유니온 파인드 편집하기

유니온 파인드(Union-Find, 병합-찾기 자료구조)는 상호 배타적 집합(disjoint-set)들을 효율적으로 표현하고 조작하기 위한 자료구조이다.
==개요==
유니온 파인드는 원소들이 어떤 집합에 속해 있는지를 빠르게 판별하고, 두 집합을 병합하는 연산을 수행하는 데 최적화된 자료구조이다. 일반적으로 상호 배타적 집합 자료구조(disjoint-set data structure)로 불리며, 대표적으로 Kruskal의 최소 신장 트리 알고리즘 등에서 사용된다. 이 자료구조는 트리를 기반으로 구현되며, 경로 압축(path compression)과 랭크(rank) 또는 크기(size)를 활용한 병합 최적화를 통해 매우 효율적인 연산 속도를 제공한다.
==연산==
유니온 파인드는 두 가지 주요 연산을 제공한다. 이 연산에서 이름이 유래되었다.
*'''Find(x):''' 원소 x가 속한 집합의 대표 원소(루트)를 반환한다.
*'''Union(x, y):''' 원소 x와 y가 속한 두 집합을 하나로 병합한다.
이 두 연산을 경로 압축과 랭크 기반 병합 전략을 함께 사용할 경우, 아커만 함수의 역함수 수준의 시간복잡도를 갖게 된다.
==구현==
유니온 파인드는 일반적으로 트리 구조와 배열을 활용하여 구현되며, 다음과 같은 형태로 구성된다:
*각 원소는 부모 노드를 가리키는 배열 parent[]를 가진다.
*초기에는 모든 원소가 자기 자신을 루트로 가지는 독립된 집합이다.
*Find 연산 시 경로 압축을 통해 트리의 높이를 줄이고,
*Union 연산 시 랭크 또는 크기에 따라 루트를 결정함으로써 전체 트리의 균형을 유지한다.
==응용==
유니온 파인드는 다양한 알고리즘 및 문제에서 활용된다.
*최소 신장 트리(MST) 알고리즘: Kruskal 알고리즘
*동적 연결성 문제(dynamic connectivity)
*네트워크 연결 상태 판별
*사이클 검출
*군집화 알고리즘에서 집합 관리
==같이 보기==
*[[그래프 이론]]
*[[최소 신장 트리]]
*[[Kruskal 알고리즘]]
*[[경로 압축]]
*[[자료구조]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
*Tarjan, R. E. (1975). Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM, 22(2), 215-225.
==각주==
[[분류:자료 구조]]