- union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명되었음 - O(M log^*{N}) - log^*{N} 은 다음 값을 가짐이 증명되었음 - N이 2^{65536} 값을 가지더라도, log^*{N} 의 값이 5의 값을 가지므로, 거의 O(1), 즉 상수값에 가깝다고 볼 수 있음 6. 크루스칼 알고리즘 (Kruskal's algorithm) 코드 작성 mygraph = { 'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'edges': [ (7, 'A', 'B'), (5, 'A', 'D'), (7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (8..

최소 신장 트리의 이해 1. 신장 트리 란? - Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임) - 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 - 신장 트리의 조건 - 본래의 그래프의 모든 노드를 포함해야 함 - 모든 노드가 서로 연결 - 트리의 속성을 만족시킴 (사이클이 존재하지 않음) 2. 최소 신장 트리 - Minimum Spanning Tree, MST 라고 불리움 - 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 3. 최소 신장 트리 알고리즘 - 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 - 대표적인 최소 신장 트리 알고리즘 - K..

4. 다익스트라 알고리즘 파이썬 구현 (우선순위 큐 활용까지 포함) 참고: heapq 라이브러리 활용을 통해 우선순위 큐 사용하기 - 데이터가 리스트 형태일 경우, 0번 인덱스를 우선순위로 인지, 우선순위가 낮은 순서대로 pop 할 수 있음 import heapq queue = [] heapq.heappush(queue, [2, 'A']) heapq.heappush(queue, [5, 'B']) heapq.heappush(queue, [1, 'C']) heapq.heappush(queue, [7, 'D']) print (queue) for index in range(len(queue)): print (heapq.heappop(queue)) 출력 [ [1, ‘C’] , [5, ‘B’], [ 2, ‘A’],..

최단 경로 알고리즘의 이해 1. 최단 경로 문제란? - 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임 - 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 1. 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 2. 단일 출발 (single-source shortest path problem) 최단 경로 문제 - 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경..

탐욕 알고리즘의 이해 1. 탐욕 알고리즘 이란? - Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 - 최적의 해에 가까운 값을 구하기 위해 사용됨 - 여러 경우 중 하나를 결정해야할 때마다, **매순간 최적이라고 생각되는 경우를 선택**하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제1: 동전 문제 - 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. - 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 - 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 coin_list = [1, 100, 50, 500] print (coin_list) coin_list..

너비 우선 탐색 (Breadth-First Search) 1. BFS 와 DFS 란? * 대표적인 그래프 **탐색** 알고리즘 - 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 - 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 - BFS 방식: A - B - C - D - G - H - I - E - F - J - 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 - DFS 방식: A - B - D - E - F - C - G - H - I - J - 한 노드의 자식을 타고 끝까지 순회한 후, 다시 ..