분리 집합이란?

분리 집합(Disjoint Set)은 **서로소 집합(Disjoint Sets)**를 표현하고 관리하기 위한 자료 구조입니다. 이 자료 구조는 주로 **집합을 합치거나(find), 특정 원소가 어떤 집합에 속하는지 확인(union)**하는 연산을 효율적으로 수행하는 데 사용됩니다.

주요 연산

find(찾기)

• 특정 원소가 속한 집합의 대표자를 찾음
• 경로 압축을 통해 최적화되어, 트리의 깊이를 최소화하여 효율성을 높임

union(합치기)

• 두 개의 집합을 하나로 합침
• 크기 기반 합치기나 랭크 기반 합치기를 사용하여 트리의 균형을 유지

알고리즘 작동 방식

1. 초기화
   • 각 원소는 독립적인 집합으로 시작, 자신이 대표자
   • Ex) [1], [2], [3], [4]
2. union
   • 두 원소가 속한 집합을 하나로 병합
   • Ex : union(1,2) → [1,2], [3], [4]
3. find
   • 특정 원소가 속한 집합의 대표자를 반환
   • Ex) find(2) → 1 (집합 [1,2]의 대표자는 1)
4. 경로 압출
   • find 연산을 수행할 때, 트리 구조를 평평하게 만들어 이후의 find 연산을 빠르게 만듦
   • Ex) 초기 트리 구조 : 1 → 2 → 3
   • find(3) 수행 후 : 1 → 2, 2 → 1, 3 → 1

장점

• find와 union 연산 모두 거의 상수 시간에 수행