Jerry's Log

Union-Find

Posted: 2025-11-17 Tags: cs algorithm

contents

Union-Find 자료 구조는 서로소 집합(Disjoint Set) 자료 구조(DSU)라고도 하며, 겹치지 않는(서로소) 여러 개의 집합으로 나뉘어 있는 항목들의 컬렉션을 추적하는 전문화된 자료 구조입니다.

이 자료 구조는 두 가지 작업을 극도로 빠르게 수행하도록 설계된, 현존하는 가장 효율적인 자료 구조 중 하나입니다.

  1. union (합집합): 두 집합을 하나로 합칩니다.
  2. find (찾기): 특정 항목이 어떤 집합에 속해 있는지 확인합니다.

이 자료 구조가 해결하는 핵심 문제

이 자료 구조는 항목들을 그룹화하고, 두 항목이 같은 그룹에 속해 있는지 확인하는 모든 문제에 대한 완벽한 해결책입니다.

비유: 소셜 클럽 🤝

여러분이 수많은 사람이 소셜 클럽을 결성하는 상황을 관리한다고 상상해 보세요.

작동 원리: 구현

이 자료 구조는 보통 parent라고 불리는 배열을 사용하여 구현됩니다.

1. 핵심 연산

DSU는 세 가지 주요 연산을 가집니다.

  1. makeSet(i): 항목 i만을 포함하는 새 집합을 초기화합니다.
    • 구현: parent[i] = i; (항목 i가 자신의 부모이므로, 자기 자신을 루트로 하는 집합의 루트가 됩니다.)
  2. find(i): i가 속한 집합의 대표(루트)를 반환합니다.
    • 구현: i로부터 부모의 연결고리를 따라가 루트를 찾을 때까지 반복합니다.
  3. union(i, j): i와 j가 속한 두 집합을 합칩니다.
    • 구현: i의 루트(root_i)와 j의 루트(root_j)를 찾습니다. 두 루트가 다르면, 한 루트가 다른 루트의 부모가 되도록 하여 두 집합을 합칩니다 (예: parent[root_i] = root_j).

최적화 없는 단순 구현 (그리고 문제점)

최적화 없이 이 연산들이 어떻게 작동하는지 봅시다.

배열: parent = [0, 1, 2, 3, 4] (모두가 자신만의 집합에서 시작)

  1. union(1, 2): find(1)은 1, find(2)는 2입니다. parent[1] = 2로 설정합니다.
    • parent는 이제 [0, 2, 2, 3, 4]
  2. union(3, 4): find(3)은 3, find(4)는 4입니다. parent[3] = 4로 설정합니다.
    • parent는 이제 [0, 2, 2, 4, 4]
  3. union(1, 3): find(1)은 2, find(3)은 4입니다. parent[2] = 4로 설정합니다.
    • parent는 이제 [0, 2, 4, 4, 4]

이제 우리가 만든 트리 구조를 보세요. 1 -> 2 -> 4 3 -> 4 4 -> 4 (루트) 0 -> 0 (루트)

문제점: find(1)을 실행하려면 1 -> 2 -> 4를 모두 거쳐야 합니다. 이는 마치 길고 한쪽으로 치우친 연결 리스트와 같습니다. 최악의 경우, union 연산이 n개 항목 모두를 일렬로 연결하여 find 연산이 O(n) 시간이 걸리게 만들 수 있습니다. 이는 매우 느립니다.

최적화 (Union-Find의 "마법")

이 문제를 해결하기 위해 두 가지 핵심 최적화가 사용됩니다. 이 둘을 함께 사용하면 알고리즘이 믿을 수 없을 정도로 빨라집니다.

1. 크기/랭크 기반 합집합 (Union by Size or Rank)

이 최적화는 배열 내의 "트리"를 평평하고 균형 잡힌 상태로 유지합니다.

2. 경로 압축 (Path Compression)

이 최적화는 find 연산 중에 트리를 극적으로 평평하게 만듭니다.

경로 압축이 적용된 find 구현 (재귀):

int find(int i) {
    // i가 루트이면, i를 반환
    if (parent[i] == i) {
        return i;
    }
    // 재귀적으로 루트를 찾고...
    // ...동시에 i의 부모를 찾은 루트로 직접 설정
    parent[i] = find(parent[i]); 
    return parent[i];
}

🚀 성능

크기/랭크 기반 합집합과 경로 압축을 모두 사용하면, 시간 복잡도는 놀라울 정도로 빨라집니다.

연산당 상각(평균) 시간 복잡도는 O(α(n)) 이며, 여기서 α(n) 은 역 아커만 함수입니다.

실제 적용 사례

references

Related Posts