Union-Find 자료구조 최적화 (Path Compression, Union by Rank)

Union-Find 자료구조는 "불일치 집합(Disjoint Set)"을 처리하는 데 매우 중요한 자료구조로, 주로 집합의 합치기(Union) 및 집합의 찾기(Find) 작업을 효율적으로 처리할 수 있도록 설계되었습니다. 이 자료구조는 다양한 알고리즘 문제에서 핵심적인 역할을 하며, 특히 그래프의 연결성 문제를 해결할 때 유용하게 사용됩니다. 예를 들어, 최소 신장 트리나 사이클 탐지와 같은 문제에서 Union-Find는 필수적인 도구입니다.

 

하지만 기본적인 Union-Find 구현은 최적화되지 않으면 비효율적일 수 있습니다. 이를 해결하기 위해 Path Compression과 Union by Rank라는 두 가지 중요한 최적화 기법이 사용됩니다. 이 글에서는 Union-Find 자료구조의 기본 개념과 두 가지 최적화 기법인 Path Compression과 Union by Rank를 자세히 다루고, 이들이 성능을 어떻게 향상시키는지 설명하겠습니다.

 

Union-Find 자료구조 기본 개념

 

Union-Find 자료구조는 두 가지 연산을 중심으로 작동합니다.

1. Find 연산:

• Find는 특정 원소가 속한 집합을 찾는 연산입니다. 주어진 원소가 속한 집합의 "대표(root)"를 찾는 작업을 합니다. Find 연산은 트리 구조로 표현되며, 트리의 루트를 찾는 방식으로 동작합니다.

2. Union 연산:

• Union은 두 개의 집합을 합치는 연산입니다. 이는 두 집합의 루트를 연결하여 하나의 집합으로 만듭니다. 이때 집합의 루트 노드를 연결하는 방식에 따라 최적화가 필요할 수 있습니다.

 

Union-Find 자료구조는 기본적으로 트리 형태로 구현되며, 트리 구조에서 루트 노드를 찾는 방법과 두 트리를 합치는 방법을 최적화할 필요가 있습니다. 두 가지 최적화 기법이 바로 Path Compression과 Union by Rank입니다.

 

1. Path Compression

 

Path Compression은 Find 연산을 최적화하는 기법입니다. 기본적으로 Find 연산은 트리 구조에서 주어진 원소가 속한 집합의 루트를 찾는 작업입니다. 그러나 트리가 매우 깊어질 경우, Find 연산이 비효율적으로 작동할 수 있습니다. 이를 해결하는 방법이 Path Compression입니다.

 

Path Compression의 동작 원리

 

• Path Compression은 Find 연산을 수행하면서, 탐색하는 경로에 있는 모든 노드의 부모를 루트 노드로 바로 연결하는 방식입니다. 이 과정은 트리의 높이를 줄여줍니다.
• 예를 들어, 원소가 속한 집합을 찾을 때, 그 집합의 루트에 직접 연결될 수 있도록 하여 이후의 Find 연산이 더 빠르게 수행되도록 만듭니다.

 

Path Compression의 효과

 

• Path Compression을 적용하면, 트리의 높이가 거의 상수에 가까운 수준으로 줄어들게 됩니다.
• 이후의 Find 연산이 매우 빠르게 수행되므로 전체적인 성능이 크게 향상됩니다.

 

예시

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # Path compression
    return parent[x]

 

위 코드는 find 함수에서 Path Compression을 구현한 예시입니다. parent[x] = find(parent[x]) 부분이 바로 경로 압축을 적용하는 부분입니다. 이 방식은 Find 연산을 수행하면서 트리의 깊이를 최소화합니다.

 

2. Union by Rank

 

Union by Rank는 Union 연산을 최적화하는 기법입니다. Union 연산은 두 집합을 합치는 연산인데, 두 트리의 루트를 연결할 때 어떤 트리를 다른 트리의 루트로 지정할지 결정해야 합니다. 이때 두 트리의 높이를 고려하여 더 작은 트리를 더 큰 트리의 자식으로 연결하는 방식이 Union by Rank입니다.

 

Union by Rank의 동작 원리

 

• Rank는 트리의 높이를 나타내며, 트리의 균형을 유지하는 데 중요한 역할을 합니다. Union by Rank는 두 트리의 루트를 합칠 때, 높이가 작은 트리를 높이가 큰 트리에 연결합니다.
• 이 방식은 트리의 높이를 최소화하여, Union 연산 후 트리가 더 균형잡히게 만듭니다.

 

Union by Rank의 효과

 

• Union by Rank를 적용하면 트리의 높이가 최소화되고, 트리의 균형이 유지됩니다.
• 트리의 높이가 적어지면 Find 연산의 속도도 빨라집니다.

 

예시

def union(x, y):
    rootX = find(x)
    rootY = find(y)
    
    if rootX != rootY:
        # Union by rank
        if rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        elif rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

 

위 코드는 union 함수에서 Union by Rank를 구현한 예시입니다. rank[rootX]와 rank[rootY]를 비교하여, 더 작은 트리를 더 큰 트리의 자식으로 연결하는 방식입니다.

 

3. Path Compression + Union by Rank

 

Path Compression과 Union by Rank를 동시에 적용하면 Union-Find 자료구조의 성능은 더욱 향상됩니다. 두 가지 최적화 기법을 결합하면, 각 연산은 아커만 함수의 역함수로 표현될 정도로 매우 빠르게 수행됩니다. 이 두 최적화 기법은 실용적인 알고리즘 문제에서 매우 중요한 역할을 하며, 시간 복잡도를 극단적으로 낮춰 줍니다.

 

결과적인 시간 복잡도

 

• Path Compression과 Union by Rank를 결합한 Union-Find 자료구조는 암호학적 상수 시간에 가까운 성능을 발휘합니다.
• 이 경우, 각 연산의 시간 복잡도는 "O(α(n))"입니다. 여기서 "α(n)"은 아커만 함수의 역함수로, 매우 느리게 증가하는 함수입니다. 사실상, α(n)은 거의 상수에 가까운 값을 가집니다.

 

결론

 

Union-Find 자료구조는 효율적인 집합 연산을 위한 강력한 도구이며, Path Compression과 Union by Rank 최적화 기법을 통해 그 성능을 극대화할 수 있습니다. 이 두 가지 기법을 결합하면, Find와 Union 연산이 매우 빠르게 수행되어, 대규모 데이터셋에서도 높은 성능을 발휘할 수 있습니다. Union-Find는 그래프 알고리즘, 최소 신장 트리, 사이클 탐지 등 다양한 문제에서 핵심적인 역할을 하므로, 이 자료구조를 최적화하여 사용하는 방법은 알고리즘 문제 해결에서 매우 중요한 기술입니다.