Computer & People

Union-Find(혹은 Disjoint Set)은 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료 구조이다. 자료 구조가 서로 다른 두 개의 집합을 병합하는 Union 연산과 집합의 원소가 어떠한 집합에 속해있는지 판단하는 Find 연산을 지원하기 때문에 Union-Find라는 이름이 붙게 되었다. 1964년 처음 고안되었다.

 * Find 연산은 하나의 원소가 어떤 집합에 속해있는지를 판단하는 연산을 말한다.

 * Union 연산은 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료 구조에서는 상호 배타적 집합만을 다루므로, Union 연산은 합집합 연산과 동치이다.

 * <math>n</math>은 모든 원소의 개수로 한다.

ArrayList에 상호 배타적 집합을 표현하기 위한 가장 간단한 방법은 배열의 각 요소에 집합의 고유 번호를 넣는 것이다. 이렇게 될 경우, 배열의 원소에 접근하는 것 만으로 속한 집합을 알 수 있게 되므로 Find 연산은 항상 <math> O(1) </math> 의 시간복잡도를 가지게 된다. 그러므로 효율적이라고 할 수 있다. 그러나 Union 연산을 수행하기 위해서는 ArrayList의 모든 원소를 순회하며 각 원소가 속한 집합 고유 번호를 바꿔 주어야 하므로 항상 <math> O(n) </math>의 시간복잡도를 가지는 것을 알 수 있다. 선형 시간이 걸리는 이 문제를, 트리 형태로 집합을 만듦으로서 해결할 수 있다.