유니온-파인드 시각화
서로소 집합을 효율적으로 관리하는 자료구조 — 경로 압축과 랭크 합치기를 시각적으로 학습합니다
그래프★☆☆
속도
1 / 1집합 수: 8노드 수: 8
U(2,4)U(3,5)U(0,3)U(0,6)U(3,7)F(2)F(6)
노드 수8
루트 노드 현재 탐색
Union-Find의 Union/Find 연산과 경로 압축 최적화 과정을 관찰하세요.
Union-Find의 Union/Find 연산과 경로 압축 최적화 과정을 관찰하세요.
유니온-파인드란?
유니온-파인드(Union-Find)는 서로소 집합(Disjoint Set)을 효율적으로 관리하는 자료구조입니다. 두 원소가 같은 집합에 속하는지 확인(Find)하고, 두 집합을 합치는(Union) 연산을 거의 O(1)에 수행합니다. 크루스칼 MST, 네트워크 연결성, 이미지 처리 등에 핵심적으로 사용됩니다.
사용 방법
- 1노드 수 슬라이더로 원소 수를 조절하세요
- 2새 연산 버튼으로 랜덤 Union/Find 연산을 생성합니다
- 3Union(a,b)는 두 집합을 합치고, Find(a)는 루트를 찾습니다
- 4같은 색 노드는 같은 집합에 속합니다
- 5경로 압축이 일어나면 트리가 평탄해지는 것을 관찰하세요
학습 팁
- •경로 압축 없이는 트리가 깊어져 O(n) 탐색이 됩니다
- •랭크 합치기는 작은 트리를 큰 트리 아래에 붙여 높이를 최소화합니다
- •경로 압축 + 랭크 합치기 = 역 아커만 함수 α(n) ≈ O(1)
- •크루스칼 MST에서 사이클 검출에 핵심적으로 사용됩니다
자주 묻는 질문
Q. 경로 압축과 랭크 합치기를 둘 다 써야 하나요?
A. 하나만 써도 O(log n)이지만, 둘 다 사용하면 O(α(n))으로 거의 상수 시간이 됩니다. 실무에서는 보통 둘 다 사용합니다.
Q. 유니온-파인드의 실무 활용은?
A. 네트워크 연결성 판단, 이미지 세그멘테이션(연결 영역 라벨링), 크루스칼 MST의 사이클 검출, 소셜 네트워크 커뮤니티 감지, 동치 관계 판단 등에 사용됩니다.