<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>
최소 신장 트리 문제
그리디 알고리즘 요구 조건
앞 절에서 모든 문제에 그리디 방식을 적용할 수 있는 것은 아니라고 했다. 즉, 최적 부분 구조(optimal substructure)와 그리디 선택(greedy choice)이라는 두 가지 속성을 모두 갖는 문제만 그리디 접근 방식으로 최적의 솔루션을 구할 수 있다.
최적 부분 구조는 큰 문제의 최적해가 부분 문제의 최적의 해답들로 구성될 수 있는 구조를 의미한다. 그리디 선택 속성은 현재의 선택이 미래의 선택에 영향을 미치지 않고, 각 단계에서 최적의 선택을 하면 전체적으로 최적의 해답을 얻을 수 있는 것을 의미한다.
이러한 특성에 대해 이해하기 위해 크루스칼 최소 신장 트리 알고리즘에 대해 알아보도록 하자.
개요
최소 신장 트리(Minimum Spanning Tree - MST)는 그래프 이론의 핵심 개념 중 하나로, 모든 정점을 포함하면서도 트리의 모든 간선의 가중치 합이 최소가 되는 트리를 찾는 문제를 의미한다. 즉, MST는 그래프의 간선에 가중치가 할당된 상황에서 최적의 해결책을 찾는 데 널리 사용된다. 예를 들어, 수도 인프라를 설계한다고 가정해보자.
수돗물을 모든 가정에 공급하기 위해서는 각각의 집을 상수도관으로 연결해야 한다. 여기서 중요한 점은 모든 가정에 수돗물을 공급하면서도 총 상수도관의 길이를 최소화하는 것이다. 각 집을 정점으로, 각 수도관을 간선으로 간주하면, 각 상수도관의 길이를 간선의 가중치로 설정할 수 있다. 이렇게 하면 MST를 구하는 문제로 변환할 수 있으며, 이를 통해 최소의 비용으로 모든 가정에 수돗물을 공급하는 네트워크를 구성할 수 있다.
크루스칼 알고리즘
이러한 최소 신장 트리 T를 구하는 대표적인 알고리즘에는 크루스칼(Kruskal) 알고리즘이 있다. 매 반복마다 최소 에지 가중치를 선택하는 이 알고리즘은 다음과 같이 총 4단계로 이루어져 있다.
- 그래프 G의 모든 에지를 최소 힙 H에 추가
- H로부터 가장 가중치가 작은 에지 e를 꺼냄
- e의 양 끝 정점이 이미 T에 있을 경우, e로 인해 T가 사이클이 발생할 수 있으므로 e를 버리고 2로 이동
- 최소 신장 트리 T에 e를 추가하고 2로 이동
이 알고리즘이 최적 부분 구조와 그리디 선택 속성을 갖는지 확인해야 한다. 이를 수학적으로 엄격하게 증명하는 것은 굉장히 어렵지만, 직관적인 방법으로 분석하고자 하면 다음 "더보기"를 눌러 확인하면 된다.
1. 그리디 선택 속성
- 크루스칼 알고리즘은 각 단계에서 그 시점에서의 가장 가벼운 간선을 선택하여 트리에 추가한다. 이는 그리디 선택의 개념에 직접적으로 부합하며, 이러한 선택이 최종 결과에 영향을 미치지 않는다. 만약 선택한 간선이 최종 MST에 포함되지 않는 경우, 이는 그 간선이 cycle을 형성하기 때문이다.
2. 최적 부분 구조
- 크루스칼 알고리즘은 MST의 부분 집합 또한 MST를 형성한다. 즉, 알고리즘이 실행되는 동안 형성되는 각 단계에서의 부분 트리는 그 자체로 MST다.
만약 수학적인 증명을 확인하고자 하면 다음 사이트를 참조하자.
디스조인트-셋 자료구조
MST는 두 가지 자료구조를 이용하여 해결할 수 있다. 먼저 간선들을 저장하고 가중치에 따라 정렬하는 과정을 vector 자료 구조를 이용하는 경우를 고려해보자. 먼저 최소 신장 T를 구하는 알고리즘은 다음과 같은 과정을 거친다고 하였다.
1단계: 모든 간선을 vector에 추가하므로, 시간 복잡도는 간선의 수 E에 비례하게 된다. 이 단계에서 시간 복잡도는 O(E)다.
2단계: vector에서 가장 작은 원소를 찾는 과정은 정렬된 벡터에서는 O(1)의 연산이 되고, 정렬되지 않은 벡터에서 최소 원소를 찾는 연산은 O(E)다. 하지만 최초에 정렬하는 과정은 대부분의 효율적인 정렬 알고리즘의 시간 복잡도 O(logE)를 따라야 하므로, O(Elog E)가 된다.
3단계: 각 정점을 확인하는 과정은 O(V)가 된다. 이때 V는 정점의 수다.
4단계: 간선을 트리에 추가하는 과정은 O(1)의 연산이다.
따라서 전체적인 시간 복잡도를 고려하면, 벡터를 사용하여 크루스칼 알고리즘을 구현할 경우, 시간 복잡도는 간선을 정렬하는데 드는 비용 O( E logE)가 가장 큰 요인이 된다.
반면 디스조인트-셋(disjoint-set) 자료 구조를 활용하면 시간 복잡도가 O(Ea(V))가 된다.
- a(V): 아커만 함수의 역함수로서 로그 함수보다 훨씬 느리게 증가함을 의미
여기서 디스조인트-셋 혹은 유니온-파인드(Union-Find)는 서로 중복되지 않는 여러 개의 원소로 구성된 집합을 분할하는 상황에서 사용하는 자료구조다. 이 자료구조는 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성되며, 각각의 원소는 하나의 트리를 나타내고, 숫자 ID에 의해 표현되며, 랭크(rank)와 부모에 대한 포인터를 가지고 있다. 또한 이 자료구조는 원소들 간의 연결 관계를 효율적으로 관리하고 집합 연산을 수행할 수 있게 해 주며, 트리 형태의 원소로 구성된 포레스트(forest)라고도 불린다.
각 집합은 대표(루트) 원소를 가지며, 원소들은 집합을 표현하는 트리 구조로 연결된다. 디스조인트-셋 자료구조는 원소들 간의 연결 상태를 효율적으로 유지하며, 집합 연산인 합집합(Union)과 찾기(Find)를 빠르게 수행할 수 있다. 이를 통해 특정 원소가 속한 집합을 신속하게 확인하거나 두 집합을 합치는 등의 연산을 효율적으로 처리할 수 있다.
- make-set(x): x를 ID로 갖는 원소를 디스조인트-셋 자료 구조에 추가. 원소의 랭크는 0이고, 원소의 부모 포인터는 자기 자신을 가리키도록 설정
- find(x): 원소 x에서 시작하여 부모 포인터를 따라 반복적으로 이동하여 트리의 루트를 반환
- union(x, y): 트리를 병합하는 함수. 두 개의 루트가 서로 다르면 높은 랭크 루트를 낮은 랭크 루트의 부모로 설정하고, 같으면 아무 작업도 하지 않음
다음은 1부터 5까지 원소로 초기화된 디스조인트-셋 자료 구조에 union 연산을 적용하는 과정이다.
디스조인트-셋을 이용했을 때 시간 복잡도가 O(Ea(V))가 되는 이유와, 이를 어떻게 구현할 지는 다음 포스팅에서 다루도록 하겠다.
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] 그리디 알고리즘 - 그래프 컬러링 (0) | 2023.05.30 |
|---|---|
| [알고리즘] 그리디 알고리즘 - 최소 신장 트리 문제 (2) (0) | 2023.05.29 |
| [알고리즘] 그리디 알고리즘 - 배낭 문제 (0) | 2023.05.23 |
| [알고리즘] 그리디 알고리즘 - 개요 및 최단 작업 우선 스케줄링 (0) | 2023.05.22 |
| [알고리즘] 분할 정복 - 맵리듀스 (0) | 2023.05.20 |