유니온 파인드 경로 압축

유니온 파인드 경로 압축(Union-Find with Path Compression)은 병합-찾기 자료구조에서 Find 연산의 효율을 극대화하기 위해 경로상의 노드들을 직접 루트 노드에 연결하는 최적화 기법이다.

개요

경로 압축은 유니온 파인드 자료구조에서 가장 중요한 최적화 기법 중 하나로, Find 연산을 수행할 때 탐색 경로에 있는 모든 노드를 해당 집합의 루트 노드에 직접 연결함으로써 트리의 깊이를 줄이고, 이후 연산의 속도를 향상시킨다. 이 방식은 특히 반복적인 Find 연산이 많은 상황에서 전체적인 시간 복잡도를 획기적으로 낮춰준다.

원리

• 유니온 파인드는 각 집합을 트리 구조로 표현하며, 각 원소는 부모 노드에 대한 포인터를 가진다.
• Find(x) 연산은 x가 속한 집합의 루트 노드를 찾는 과정이다.
• 경로 압축은 이 Find 과정 중에 탐색한 모든 중간 노드들을 루트 노드에 직접 연결하여 트리의 높이를 평탄화(flatten)한다.
• 이러한 평탄화는 이후의 Find 연산을 거의 상수 시간으로 수행 가능하게 만든다.

구현 방식

경로 압축은 재귀 또는 반복 방식으로 구현할 수 있으며, 가장 일반적인 재귀적 구현은 다음과 같다:

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

이 구현에서는 parent[x]가 x 자신이 아닐 경우, 루트를 재귀적으로 찾은 뒤, 해당 루트를 parent[x]에 직접 저장함으로써 x에서 루트까지의 경로를 1로 만든다.

시간 복잡도

경로 압축은 랭크 기반 병합(Union by Rank)과 함께 사용할 때 특히 효율적이며, n개의 원소에 대해 m개의 연산을 수행할 경우 전체 시간 복잡도는 O(m α(n))이 된다. 여기서 α(n)은 아커만 함수의 역함수이며, 모든 실용적인 n에 대해 5 이하의 값을 가지므로 사실상 상수 시간에 가까운 성능을 제공한다.

효과

• 트리의 깊이를 빠르게 평탄화시켜 Find 연산을 거의 O(1) 시간으로 수행 가능하게 한다.
• Union 연산과 함께 사용될 경우, 전체 유니온 파인드 시스템의 성능을 극대화한다.
• 여러 번의 Union과 Find가 반복되는 알고리즘(예: Kruskal 알고리즘)에서 뛰어난 성능을 보장한다.

경로 압축 vs 랭크 기반 병합

• 경로 압축은 Find 연산의 최적화를 위한 기법이며, 랭크 기반 병합은 Union 연산 시 트리의 균형을 위한 전략이다.
• 두 기법은 서로 보완적이며 함께 사용될 때 최고의 성능을 발휘한다.

같이 보기

• 유니온 파인드
• 랭크 기반 병합
• 최소 신장 트리
• 크루스칼 알고리즘
• 자료구조

참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Tarjan, R. E. (1975). Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM, 22(2), 215-225.