다익스트라 알고리즘: 백준 1916

다익스트라 알고리즘Dijkstra 알고리즘은 그래프에서 최단 거리를 구하는 문제를 푸는 대표적인 알고리즘이다. 기본 알고리즘은 $O(N^2)$ 시간 복잡도를 가지지만, 우선순위 큐를 이용해 $O(NlogN)$로 최적화할 수 있다. 문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. - 백준 1916문제를 도식화하면 위와 같다. 1번 도시에서 출발해 5번 도시에 도착한다. 이때 가장 짧은 거리로 이동하려 한다. 풀이다익스트라 알고리즘은 생각보다 간단하게 작동한다.출발점으로부터 ..

• format_list_bulleted 기타 주제/자료구조 & 알고리즘
• · 2024. 3. 10.

소수 구하기: 백준 1929

에라토스테네스의 체는 $O(nlog(logn))$의 시간 복잡도를 가지는 알고리즘으로, 효율적으로 소수(Prime Number)를 구할 수 있다. 소수: 1과 자기 자신 만을 약수로 가지는 수 아이디어는 간단하다. 자연수 N이 있을 때, N의 배수는 소수가 아니다. 소수는 1과 자기 자신만을 약수로 가지는데, N의 배수는 N을 약수로 가지기 때문이다. 소수의 정의를 생각해 보면 당연한 이야기이다. 1 ~ 100까지의 수가 있는 표를 만들자. 그리고 만약 소수가 아니라면 표에서 값을 지운다. 0과 1은 소수가 아니다. 0 1 2 3 4 5 6 7 8 ... 2는 소수이다. 하지만 2의 배수는 소수가 아니다. 따라서 4, 6, 8 ... 등은 지운다. 0 1 2 3 4 5 6 7 8 ... 3은 소수이다. ..

• format_list_bulleted 기타 주제/자료구조 & 알고리즘
• · 2023. 10. 3.

Quick Sort 원리와 구현 (Python, Go)

Quick Sort는 분할 정복을 이용한 정렬 알고리즘으로 평균적으로 좋은 성능을 보인다. 평균 시간 복잡도: $O(nlog_2n)$ 정렬된 리스트에 대해: $O(n^2)$ 정렬 원리 1 퀵 정렬의 아이디어는 생각보다 간단하다. 기준을 정한다. 기준보다 작으면 기준점의 왼쪽으로, 기준보다 크면 기준점의 오른쪽으로 모은다. 기준의 왼쪽과 오른쪽의 배열을 쪼갤 수 없을 때까지 재귀적으로 정렬한다. 이때 기준점을 pivot이라고 한다. 배열의 첫번째 값을 pivot으로 설정한 예시: 1. [5 4 3 1 6 2 7] 2. pivot: 5 [4 3 1 2] + [5] + [6 7] 3. pivot: 4, 6 [3 1 2] + [4] + [5] + [6] + [7] 4. pivot: 3, (우측은 정렬 완료) [..

• format_list_bulleted 기타 주제/자료구조 & 알고리즘
• · 2023. 9. 3.

B+Tree로 DB 탐색

데이터 인덱스를 어떤 자료구조로 정렬하냐에 따라 탐색 시간이 달라진다. 일반적으로 많이 사용되는 구조가 B+Tree이다. B+Tree는 아래와 같은 특징을 갖는다. 작은 값은 왼쪽 자식, 크거나 같은 값은 오른쪽 자식에 속한다. Leaf 노드만 데이터 포인터이며, 내부의 노드는 인덱스를 찾기 위한 역할을 한다. 만약 트리 내부에 7이 있더라도 Leaf 노드에 7이 없다면 데이터를 찾을 수 없다. Leaf 노드는 연결 리스트로 연결된 선형 구조를 가진다. 0 → 5 → 6 → 8 → ... 하나의 노드에 저장할 수 있는 최대 인덱스 개수를 fanout이라고 한다. 위 그림은 fanout이 4이다. fanout이 f이고, 데이터가 N개일 때, $\left \lceil log_fN \right \rceil$ ..

• format_list_bulleted 기타 주제/자료구조 & 알고리즘
• · 2022. 11. 30.

탐색 알고리즘 - DFS, BFS

DFS (Depth-Fisrt Search) DFS: 깊이 우선 탐색 트리 상에서 자식 노드가 있다면, 아래(자식 노드)로 계속 전진하여 탐색하는 방법. 위 그림에서 각 노드의 번호는 탐색 순서를 뜻한다. 1번 노드는 2, 5번 노드를 자식으로 가진다. 하지만 2번 노드가 자식 노드를 가지기 때문에 5번 노드를 탐색하기 전 3, 4번 노드를 우선 탐색한다. 2번 노드에 다른 자식 노드가 없기 때문에 다시 5번 노드를 탐색하는 형태이다. 구현 - Python - open 리스트: 탐색하지 않은 상태(노드)들 - close 리스트: 탐색을 마친 상태(노드)들 DFS는 스택(stack)을 이용하여 구현할 수 있다. (FILO) def dfs(graph, start_node): # open list: stack..

• format_list_bulleted 기타 주제/자료구조 & 알고리즘
• · 2022. 3. 8.

재귀 함수 - 하노이 탑 문제

하노이 탑 문제: 3개의 기둥이 있으며 한 기둥에 원판들이 쌓여있다. 그리고 아래 규칙에 따라 원판을 다른 기둥으로 이동시켜야 한다. 규칙: 한 번에 하나의 원판을 이동시킬 수 있으며, 큰 원판이 작은 원판 위에 있으면 안 된다. 문제 해결 문제를 일반화하기 전, 3개의 원판을 가진 하노이탑 문제를 고민해보면 아래 그림과 같다. 3개의 원판을 이동시키기 위해서는 먼저 2개의 원판을 임시 기둥(B)으로 옮겨야 한다. 그런 후, 가장 큰 원판을 목표 기둥(C)으로 옮길 수 있다. 같은 원리로 2개의 원판을 목표 기둥(B)으로 이동하기 위해서는 임시 기둥(C)으로 작은 원판을 이동해야 한다. 문제 일반화 1. n개의 원판을 옮기기 위해 n-1개의 원판을 목표 기둥이 아닌 임시 기둥으로 옮겨야 한다. (n≥2)..

• format_list_bulleted 기타 주제/자료구조 & 알고리즘
• · 2022. 3. 4.