Computer Science/DataStructure
Disjoint Set (분리 집합)
Disjoint Set 분리 집합 또는 서로소 집합은 각각의 집합이 공통 원소를 가지고 있지 않은 집합이다. 즉 전체집합 U에 대해, U의 분리 집합 A ,B는 다음 조건을 만족한다. A, B는 U의 부분 집합이다. A, B는 공통 원소를 가지지 않는다. (A ∩ B = Ø) A, B의 합집합은 전체 집합 U이다. (A ∪ B = U) 위 조건은 분리 집합이 개수가 3개 이상일때도 만족한다. Union-Find Union-Find는 분리 집합을 구현하고 조작하는 자료구조이다. 분리 집합을 합치는 연산인 union 연산과 임의의 원소가 어떤 집합에 속하는지 찾는 find 연산을 제공한다해서 union-find 자료구조라 불린다. Union-Find를 구현하기 위해선 아래 3가지 연산을 구현해야한다. 초기화..
