유니온-파인드
-
디스조인트-셋(disjoint-set) :: 마이구미알고리즘 2017. 11. 5. 17:27
이 글은 디스조인트-셋(disjoint-set) 자료구조를 다룬다.유니온-파인드(union-find) 라고도 불리고, 머지-파인드-셋이라고도 불리는 자료구조이다.위키백과 - 디스조인트-셋 디스조인트-셋은 해석하면 서로소 집합이라고 표현할 수 있다.서로소 집합이란, 공통된 원소가 없는 집합으로써, 교집합이 공집합인 집합이라고 보면 된다. 디스조인트-셋을 활용하기 위해서는 다음과 같은 정의를 확실히 이해해야한다. 많은 상호 배타적 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조. "상호 배타"와 "독립"을 혼동해서는 안된다.독립은 집합으로 표현하면 다음과 같다. A ∩ B = 0, A ∪ B = U A와 B 사이에는 어떠한 관계도 존재하지 않다는 것을 알 수 있다.상호 배타는 다음과 같..