| 작성자 | 장원준 |
| 일 시 | 2024. 11. 19 (화) 18:00 ~ 21:00 |
| 장 소 | 복지관 B-128-1호 |
| 참가자 명단 | 임혜진, 장원준, 이재영, 성창민, 김명원 |
| 사 진 |  |
서로소 집합 (Disjoint Set)이란 무엇인가?
서로소 집합(Disjoint Set)은 이름 그대로, 서로 공통된 원소가 없는 집합들을 다루는 자료구조입니다. 예를 들어, 어떤 집합에 속하는 원소들이 다른 집합과는 완전히 구별되는 경우, 이들 집합을 서로소 집합이라고 합니다. 이 구조는 주로 그래프 알고리즘이나 네트워크 연결성 문제를 해결할 때 많이 사용됩니다. 즉, 서로 다른 원소들이 같은 집합에 속해있는지 여부를 확인하는 데 유용합니다.
Disjoint Set 자료구조의 주요 연산
서로소 집합 자료구조는 크게 세 가지 연산을 제공합니다: MakeSet, Union, Find. 각각의 연산이 어떻게 작동하는지 살펴보겠습니다.
1. MakeSet
MakeSet 연산은 각 원소를 독립된 집합으로 초기화합니다. 초기화할 때는 각 원소를 포함하는 집합을 하나씩 만들어줍니다. 이 과정에서는 `parent` 배열을 생성하는데, 이 배열은 각 노드의 부모 노드를 가리킵니다. 부모 노드가 없는 경우 자기 자신을 부모로 설정합니다. 이 `parent` 배열은 이후 `Union`과 `Find` 연산에서 사용됩니다.
2. Find
Find 연산은 특정 원소가 속한 집합의 대표 원소(루트 노드)를 찾는 연산입니다. `parent` 배열을 재귀적으로 순회하면서 최종적으로 대표 원소에 도달할 때까지 탐색합니다. 이렇게 찾은 대표 원소는 해당 집합을 대표하는 값이 됩니다.
3. Union
Union 연산은 두 개의 집합을 하나로 병합합니다. 병합한 집합은 하나의 대표 원소를 공유하게 되며, 이 대표 원소를 `Find` 연산을 통해 확인할 수 있습니다.
성능 개선: 트리 구조 최적화
Disjoint Set의 성능은 트리의 높이에 따라 크게 달라집니다. 트리 높이가 높아지면 `Find` 연산이 느려질 수 있기 때문에 이를 최소화하는 두 가지 기법이 있습니다.
1. 경로 압축 (Path Compression): `Find` 연산을 수행할 때마다 방문한 노드들이 루트 노드를 직접 가리키도록 재구성합니다. 이로 인해 트리가 평평해져 이후 `Find` 연산을 O(1)에 가까운 속도로 수행할 수 있습니다.
2. 랭크 기반 합치기 (Union by Rank): 트리의 높이가 낮은 집합을 높이가 높은 집합에 병합하여 트리의 높이를 줄이는 방법입니다.
서로소 집합은 효율적인 그래프 탐색과 네트워크 문제 해결에 중요한 기초 개념으로, 이해하고 활용하는 데 큰 도움이 될 것입니다.
Disjoint set 알고리즘을 공부해보며 트리구조 최적화에 대해 생각해보게 되었습니다.
경로 압축을 통해서 트리를 평평하게 하는 것은 이해가 쉽게 되었으나 트리 높이가 낮은 집합을 높이가 높은 집합에 병합하는 방법은 생각하지 못한 아이디어여서 뜻깊은 공부가 되었습니다.