프로그래머스에서 섬 연결하기 문제를 Kruskal 알고리즘으로 풀면서 공부한 것을 정리한 내용이다!
최소 신장 트리 (Minimum Spanning Tree)란?
먼저 Kruskal 알고리즘을 이해하기 전에 최소신장트리(MST)를 알아야 한다.
MST란 간선에 가중치가 있을 때, 모든 정점을 방문하면서 비용을 최소로하는 트리를 의미한다.
이때 그래프에 사이클이 포함되면 안된다.
위 그림을 보면 가중치가 포함된 그래프가 주어질 때, 오른쪽 그림의 간선을 연결함으로써 최소 비용으로 모든 노드를 방문할 수 있는 트리가 만들어지게 된다.
최소신장트리를 구현하는 알고리즘에는 대표적 Kruskal과 Prim 알고리즘이 있다.
오늘은 Kruskal 알고리즘에 대해서만 알아보자.
Kruskal 알고리즘이란?
Kruskal 알고리즘은 Greedy 방식(탐욕적 방식)을 이용하여 MST를 구하는 알고리즘이다.
그래프에서 주어지는 간선들을 가중치에 대한 오름차순으로 정렬했을 때, 매 순간마다 가장 최선의 선택을 하면서 최종 트리를 도출하는 방식이다.
이때 매 순간마다 최선의 선택은 이전 선택이나 다음 선택에 관여받지 않는다 (Greedy 알고리즘의 핵심!)
간선을 선택할 때 주의해야할 점은 사이클을 생성하지 않는 간선이어야한다!
Kruskal 알고리즘의 시간 복잡도
Kruskal 알고리즘의 시간복잡도는 간선을 정렬하는 시간복잡도에 비례한다.
(Kruskal 내부적인 서로소 집합 알고리즘의 시간복잡도가 정렬 알고리즘 시간보다 작기 때문이다.)
즉 정렬알고리즘을 어떤걸 선택하냐에 따라 달라지는데, 퀵정렬과 같은 빠른 알고리즘을 사용한다면 O(ElogE)의 시간이 걸린다.
+) Python에서 .sort() 함수를 사용하는 경우 퀵 정렬을 사용하므로 O(NlogN)의 시간이 걸린다.
'자료구조, 알고리즘' 카테고리의 다른 글
[알고리즘] CodeForce 해시 알고리즘 구현 (Python) (0) | 2023.05.29 |
---|---|
[자료구조] 큐 (Queue) (0) | 2022.04.01 |
[자료구조] 스택 (Stack) (0) | 2022.04.01 |
[자료구조] 원형 연결 리스트 (Circular Linked List) (0) | 2022.03.04 |
[자료구조] 연결 리스트(Linked List) (0) | 2022.03.01 |