출시·고도화 중
Algorithm
유니온 파인드(서로소 집합)는 원소를 겹치지 않는 묶음으로 나누고, 두 원소가 같은 묶음인지 판단하거나 두 묶음을 합치는 일을 거의 상수 시간에 처리합니다.
유니온 파인드는 서로소 집합(disjoint set) 자료 구조라고도 부르며, 원소들을 겹치지 않는 여러 집합으로 나누어 관리합니다. 두 가지 연산만 제공합니다. find는 원소가 속한 집합의 대표 원소를 찾고, union은 두 원소가 속한 집합을 하나로 합칩니다. 각 집합은 부모를 가리키는 트리로 저장되며, 트리의 루트가 그 집합의 대표입니다.
연결이 늘어나기만 하는 상황에서 "이 둘이 이어져 있는가?"를 반복해서 물어야 할 때, 매번 그래프를 탐색하는 대신 유니온 파인드를 쓰면 훨씬 빠릅니다. 경로 압축과 랭크·크기 기준 합치기를 함께 쓰면 연산 한 번의 분할 상환 비용이 역 아커만 함수 α(n)로 줄어드는데, 이 값은 현실의 어떤 입력에서도 4를 넘지 않습니다. 크루스칼 최소 신장 트리, 사이클 판별, 연결 요소 계산, 계정 병합 같은 그룹화 문제의 기본 도구이며 코딩 테스트에도 자주 나옵니다.
먼저 parent 배열 하나로 find와 union을 직접 구현하고, 최적화 없이 트리가 한 줄로 길어지는 경우를 손으로 따라가 보세요. 그다음 크기 기준 합치기와 경로 압축을 하나씩 더하며 트리 깊이가 어떻게 바뀌는지 확인하면 원리가 분명해집니다. 마지막으로 연결 요소, 사이클 판별, 크루스칼 문제를 풀어 보며 union의 반환값을 활용하는 습관을 들이면 됩니다.
find는 부모를 따라 루트(대표 원소)를 찾고, union은 두 루트 중 하나를 다른 루트 밑에 붙여 집합을 합칩니다.
find가 지나간 노드를 루트에 직접 연결해 트리를 납작하게 만들므로 이후 호출이 빨라집니다.
작은 트리를 큰 트리 밑에 붙여 트리 높이를 log n 이하로 유지합니다.
두 최적화를 함께 쓰면 연산 m번이 O(m α(n))에 끝나며, 역 아커만 함수 α(n)은 사실상 4 이하입니다.
DSU 클래스는 parent와 size 배열 두 개로 집합을 저장합니다. find는 부모를 따라 올라가며 각 노드를 할아버지에 붙이는 경로 반감으로 트리를 납작하게 만들고, union은 작은 집합을 큰 집합 밑에 붙이며 이미 같은 집합이면 False를 돌려줍니다. 예제는 원소 6개를 세 묶음으로 합친 뒤 같은 집합인지와 집합 개수를 출력합니다.
union_find.py
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
dsu.union(a, b)
print(dsu.find(2) == dsu.find(0)) # True
print(dsu.find(4) == dsu.find(5)) # False
print(len({dsu.find(x) for x in range(6)})) # 3
python union_find.py설치부터 유니온 파인드 의 핵심 개념까지, 여섯 장으로 차근차근 따라 합니다.
유니온 파인드 에 관해 묻고, 경험을 나누고, 의견을 주고받는 곳입니다.
아직 토론이 없습니다. 첫 이야기를 시작해 보세요.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.
첫 댓글을 남겨 보세요.