코딩테스트 - 패스트캠퍼스 챌린지 19일차

수강한 강의
Chapter 20 그래프 고급 탐색 알고리즘
- 최소 신장 트리의 이해와 크루스칼 알고리즘

학습 후기
신장 트리(Spanning Tree)는 모든 노드들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. n개의 노드로 이루어진 그래프는 n-1개의 간선으로 연결된다.

최소 신장 트리(Minimum Spanning Tree, MST)
최소 신장 트리는 Spanning Tree 중
1. 사용된 간선의 가중치 합이 최소이고
2. n개의 노드를 가지는 그래프에서 간선이 n-1개이고
3. 사이클이 포함되지 않은 트리이다.

크루스칼 알고리즘(Kruskal Algorithm)
그래프에서 최소 신장 트리(MST)를 찾는 알고리즘으로 탐욕 알고리즘에 기초하여 각 단계에서 사이클을 이루지 않는 최소 비용의 간선을 선택하고 결과적으로 최적의 경로(최소 비용)를 찾는 알고리즘이다.

크루스칼 알고리즘 과정
1. 간선들의 가중치를 정렬한다.
2. 정렬된 간선들을 순회하며 사이클을 형성하지 않는 간선을 선택한다.
- 사이클을 형성하는 간선은 제외한다.
3. 선택된 간선을 최소 신장 트리 리스트에 추가한다.

이번 강의에서 크루스칼 알고리즘을 구현할 때 간선을 선택하고, 간선들을 서로 연결할 때 Union-Find 알고리즘을 사용한다.

Union-Find 알고리즘
Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘이다.
Disjoint Set는 서로소 집합 자료구조로 집합의 부분집합을 만들 때 공통 원소가 없는 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미한다.

Union-Find 알고리즘 함수
1. 초기화: n개의 원소를 각각 개별 집합으로 초기화
2. Union: 두 집합을 하나의 집합으로 합침
3. Find: 두 개의 노드가 서로 같은 그래프에 속하는지 판별하기 위해 루트 노드를 확인
Union-Find 알고리즘은 최악의 경우 링크드 리스트와 같은 형태가 될 수 있기 때문에 이 경우 복잡도가 O(N)이 되는데 이 문제를 해결하기 위해 union-by-rank, path compression 기법을 사용한다.
union-by-rank: 트리의 높이를 기억하고 서로 다른 높이의 트리를 합칠 때 높이가 작은 트리를 큰 트리에 붙임, 이렇게 하면 O(N)을 O(log N)으로 낮출 수 있음.
path compression: Find를 실행하여 거쳐간 노드의 루트를 직접 연결, 그 이후에 루트 노드를 찾을 때 바로 찾을 수 있다.

시간 복잡도
크루스칼 알고리즘의 시간 복잡도는 다음 과정에서 영향을 받는다.
1. 모든 노드를 독립적인 집합으로 만든다.
2. 모든 간선을 가중치 기준으로 정렬한다.
3. 두 노드의 최상위 노드를 확인하고, 서로 다를 경우 두 노드를 연결한다.
1번은 O(V), 2번은 퀵 소트를 사용한다면 O(E log E), 3번은 간선을 순회하며 Union-Find 알고리즘의 union-by-rank와 path compression 기법을 사용한다면 O(E) * O(1) = O(E).
따라서 총 시간 복잡도는 O(E log E)가 된다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.