유니온 파인드(Union-find, 서로소 집합)

유니온 파인드(Union-Find) 알고리즘, 또는 서로소 집합(Disjoint Set) 자료구조는 동적 연결성 문제를 해결하기 위해 사용된다. 이 자료구조는 주로 그래프에서 연결된 컴포넌트를 찾는 데 사용되는데, 유니온 파인드 자료구조는 두 가지 주요 연산을 효율적으로 수행한다.

1. Union: 두 개의 집합을 하나의 집합으로 합친다.
2. Find: 특정 원소가 속한 집합을 찾는다.

유니온 파인드의 주요 개념

1. 집합 표현:
   • 각 원소는 자신을 부모로 가지는 트리 형태로 표현된다.
   • 집합의 루트 노드는 집합의 대표(또는 루트)로 간주된다.
2. Find 연산:
   • 주어진 원소가 속한 집합의 대표를 찾는다.
   • 경로 압축(Path Compression)을 통해 트리의 높이를 줄여, 이후의 Find 연산이 더 빠르게 수행되도록 최적화할 수 있다.
3. Union 연산:
   • 두 개의 집합을 하나로 합친다.
   • Union by Rank 또는 Union by Size 기법을 사용하여 트리의 높이를 최소화할 수 있다.

유니온 파인드의 최적화 기법

1. 경로 압축(Path Compression):
   • Find 연산을 수행하는 동안, 방문한 모든 노드를 직접 루트 노드에 연결하여 트리의 높이를 줄인다.
   • 이 최적화는 Find 연산의 시간 복잡도를 거의 상수 시간으로 만든다.
2. 랭크에 의한 합치기(Union by Rank):
   • 각 트리의 높이를 추적하고, 항상 높이가 낮은 트리를 높이가 높은 트리 아래에 연결하여 트리의 높이를 최소화한다.
   • 이는 트리의 균형을 유지하는 데 도움이 된다.
3. 크기에 의한 합치기(Union by Size):
   • 각 집합의 크기를 추적하고, 항상 작은 트리를 큰 트리 아래에 연결하여 트리의 높이를 최소화한다.
   • 이는 Union by Rank와 유사하게 트리의 균형을 유지하는 데 도움이 된다.

시간 복잡도

경로 압축과 랭크에 의한 합치기 최적화를 적용하면 유니온 파인드 자료구조의 연산은 거의 상수 시간으로 수행되는데, 정확히는 매우 느리게 증가하는 역 아커만 함수(inverse Ackermann function) 시간 복잡도인 O(α(n))으로 수행한다. 이 함수는 실제로는 거의 상수로 간주될 수 있다.