전체 글

[자료구조] 그래프(Graph) + 구현하기(Java의 인접행렬과 인접리스트)

그래프(Graph)란? 그래프란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 그래프는 정점(vertex)과 정점과 정점을 연결하는 간선(edge)들의 집합으로 구성된다. -> 정점(vertex)는 노드(node)라고도 함 아래는 대표적인 그래프 종류들의 예시이다. 그렇다면 이러한 그래프를 구현하는 방법에 대해 알아보자. 그래프 구현하기 컴퓨터에서 그래프를 구현하는 방법에는 배열(Array)를 사용하는 방법과 연결리스트(Linked List)를 사용하는 방법이 있다. 그래프 구현 - 인접 행렬(Adjacency Materix) 정점 a와 정점 b를 잇는 간선이 있을 경우, 행렬(a,b)에 1을 표기해준다. 만약 가중치가 있는 그래프라면 1 대신 가중치를 넣을 수 있다. 기본적으로 무..

[알고리즘] Brute Force(브루트 포스)

Brute Force(브루트 포스) 브루트 포스는 Brute : 난폭한 / Force : 힘 => 난폭한 힘으로 해석이 된다. 이를 설명하면, 무식하게 모든 경우의 수를 탐색(완전탐색)하면서 조건에 충족되는 결과만을 가져온다. 이 알고리즘의 가장 큰 특징은 모든 영역을 전체 탐색하는 방법이다. 전체 탐색하는 방법으로는 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 백트래킹(Backtracking) 가 기본적인 도구이다. 어떤 방식으로든 전체 탐색으로 문제를 해결한다면 브루트 포스 알고리즘으로 풀었다고 할 수 있다. 브루트 포스는 완벽히 모든 경우의 수를 탐색하기에, 정확도는 우수하지만, 자원을 너무 많이 사용한다는 점에..

도커 타임존(timezone) 변경

도커 컨테이너 내의 timezone(default: UTC)를 변경해주기 위해서는 docker run할때 -e TZ=Asia/Seoul 옵션으로 변경해 줄 수도 있지만, tzdata를 이용해 쉽게 변경 할 수 있다. export TZ=Asia/Seoul 컨테이너 내에서 위의 명령어를 입력하고, date명령어로 시간을 확인해보면 에서 로 변경된 것을 볼 수 있다. 위와 같이 했는데도, 컨테이너를 나갔다가 들어왔을때 적용이 안되어있다면 아래와 같은 방법으로 해보는 것을 추천한다. -컨테이너 접속 후 # dpkg-reconfigure tzdata - 한국 서울 기준 6(Asia) -> 69(Seoul) 선택 # date로 변경된 시간 확인 후 docker 재시작 추가> DB TimeZone 변경하기 http:..

[자료구조] B-tree, B+tree 이론 정리

B-tree "데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다." 정리하자면, B-tree는 Binary search tree와 유사하지만, 한 노드 당 자식 노드가 2개 이상 가능하다 라고 할수있다. 여기서 먼저 트리구조에 대해 알아보자. 트리 구조는 꼭 데이터베이스에 한정하지 않더라도 시스템 세계에서는 데이터를 유지하기 위해 자주 사용하는 구조이다. '탐색' 시, 단시간 내에 실행할 수 있기 때문이다. B-tree의 핵심은 데이터가 정렬된 상태로 유지되어 있다는 것이다. 그림에 표시된 사각형으로 표시된 한 개 한 개의 데이터를 '노드(Node)'라고 한다. 가장 상단의 노드를 '루..

[Java] 카운팅 정렬 (Counting Sort)

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 백준 10989번 수 정렬하기3 문제를 Collections.sort()로 오름차순 정렬했더니 아래와 같은 메모리 초과 오류가 떴다. 구글링을 통해 알아보았더니, Collections.sort()나 Arrays.sort()같은 메소드는 평균 시간복잡도가 𝚶(nlogn) 인 반면에 Counting sort는 평균 시간복잡도가 𝚶(𝑛) 인 성능을 보여주는 알고리즘인 것을 알게 되었다. Arrays.sort()는 평균: ..