Disjoint Set
12 Nov 2017 | partition
이번 글에서는 디스조인트 셋(Disjoint Set)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아, 그리고 이곳을 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
디스조인트 셋이란 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조입니다. 디스조인트 셋은 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할(partition)하는 데 자주 쓰입니다. 이와 관련해 몇 가지 용어를 살펴보겠습니다.
- 셋(set)은 개체들의 집합입니다. (리스트 등과 달리 순서는 고려하지 않음)
- 셋 $A$의 모든 원소가 셋 $B$에 포함될 때 $A$를 $B$의 부분집합(subset)이라 합니다. 이 때 $B$는 $A$의 초월집합(superset)이라 합니다.
- 셋 $A$와 셋 $B$가 공유하는 원소가 하나도 없을 때 $A$와 $B$를 mutually disjoint하다고 합니다.
- 임의의 셋을 분할(partition)한다는 건 각 부분집합이 다음 두 가지 속성을 만족하는
디스조인트 셋이 되도록 셋을 쪼개는 걸 뜻한다. (1) 파티션된 부분집합을 합치면 원래의 셋이 된다. (2) 파티션된 부분집합끼리는 mutually disjoint, 즉 겹치는 원소가 없다.
예컨대 $S={1,2,3,4}$이고, $A={1,2}$, $B={3,4}$, $C={2,3,4}$, $D={4}$라면 $A$와 $B$는 $S$의 분할입니다. 이 때 $A$와 $B$가 디스조인트 셋입니다. 하지만 $A$와 $C$는 $S$의 분할이 아닙니다. 겹치는 원소가 있기 때문입니다. $A$와 $D$ 또한 $S$의 분할이 아닙니다. 둘을 합쳐도 $S$가 되지 않기 때문입니다.
operations
디스조인트 셋은 세 가지 연산이 있는데요. make-set은 초기화 연산이므로 union과 find가 핵심이라고 할 수 있겠습니다.
- make-set(x) : $x$를 유일한 원소로 하는 새로운 셋을 만듭니다.
- union(x, y) : $x$가 속한 셋과 $y$가 속한 셋을 합칩니다.
- find(x) : $x$가 속한 셋의 대표값(루트노드 값)을 반환합니다.
예를 들어 보겠습니다. $A={3,4}$인 디스조인트 셋이 이미 만들어져 있다고 칩시다. 이 경우 첫번째 들어간 원소인 3이 루트노드가 되며 3이 $A$를 대표하는 값이 됩니다. 다음과 같습니다.
find(4)는 4가 속한 셋의 대표값을 출력하라는 뜻입니다. 따라서 이 예에서는 3이 됩니다. 마찬가지로 find(3) 또한 출력 결과가 3입니다.
이번엔 다른 디스조인트 셋 $B={1,2}$가 있다고 치겠습니다. $B$의 대표값은 루트노드인 1입니다. $A$와 $B$를 합칠 때는 루트노드들끼리 이어줍니다. 다음과 같습니다.
새롭게 만든 디스조인트 셋의 루트노드는 1입니다. 따라서 예컨대 4가 속한 셋의 대표값을 출력하라는 $find(4)$를 수행하면 출력 결과가 1이 됩니다.
array로 구현
디스조인트 셋의 세 가지 기본연산을 배열(array)로 구현해보겠습니다. $A={3,4}$, $B={1,2}$ 이렇게 두 개 디스조인트 셋이 이미 만들어져 있다고 칩시다.
이를 배열로 구현하면 다음과 같습니다. $N$은 입력원소들을 가리킵니다. $S$는 입력원소가 루트노드인지 아닌지, 부모노드가 어떤 위치에 있는지 나타냅니다. 예컨대 3과 1은 루트노드이기 때문에 이들에 해당하는 $S$의 값이 0입니다. 4의 부모노드는 $N$의 첫번째 요소, 즉 3이라고 표시가 되어 있네요. 마찬가지로 2의 부모노드는 $N$의 세번째 요소, 즉 1입니다.
- $N=[3,4,1,2]$
- $S=[0, 1, 0, 3]$
union 연산을 하면 $S$가 다음과 같이 바뀝니다.
- $S=[0, 1, 1, 3]$
그렇다면 union(x,y) 연산의 계산 복잡성은 얼마나 될까요? 크게 세 가지 단계로 나눠 생각해볼 수 있습니다.
- $x$가 속한 디스조인트 셋을 찾아야 합니다 : find(x)
- $y$가 속한 셋을 찾아야 합니다 : find(y)
- 찾은 셋을 합칩니다.
그런데 생각해보면 find 연산의 계산복잡성은 디스조인트 셋의 원소 수가 $n$개일 때 $O(\log{n})$입니다. 부모노드를 반복적으로 역추적해 루트노드를 찾습니다. 예컨대 잎새노드에서 루트에 이르기까지 일렬로 3-4-5-2-1 이렇게 구성돼 있는 디스조인트 셋이 있다고 할 때 find(3)은 엣지를 트리의 높이만큼 네 번 거슬러 올라가야 루트인 1을 찾을 수가 있습니다. find 연산을 좀 더 효율적으로 수행하기 위한 방법이 바로 path compression인데 조금 있다가 다루겠습니다.
find 연산을 두 번 수행해 합칠 셋을 찾았다고 칩시다. 그러면 이제 이 두 셋을 합칠 차례입니다. 합치는 방법에는 union-by-size와 union-by-height가 있는데 바로 다음에서 다루겠습니다.
union
임의의 두 디스조인트 셋을 합칠 때는 원소수가 적은 셋을 많은 셋의 서브트리로 합치는 것이 효율적입니다(union-by-size). 마찬가지로 트리의 높이가 작은 셋을 큰 셋의 서브트리로 합쳐야 합니다(union-by-height). 다음 union 연산 때 반드시 find 연산을 수행해야 하는데 find 연산의 효율성을 높여주기 위해서입니다. 원소수와 트리의 높이는 비례하는 경향이 있고 find 연산의 계산복잡성은 이들에 매우 의존적입니다.
union-by-size와 union-by-height를 구현하는 것은 간단합니다. 배열 $S$의 루트노드 정보를 바꾸면 됩니다. 루트노드일 때 0을 넣었던 기존과 달리 다음과 같이 바꿉니다.
- union-by-size : $-$size of tree
- union-by-height : $-$height of tree
요컨대 find 연산에서 찾은 두 개 디스조인트 셋의 원소수 혹은 높이를 비교해서 더 큰 쪽으로 합쳐줍니다. 이렇게 하면 이후 find 연산을 조금 더 효율적으로 수행할 수 있습니다.
union-by-size와 union-by-height의 계산복잡성은 $O(1)$입니다. find 연산에서 이미 두 디스조인트 셋의 루트노드를 찾았기 때문에 $S$에서 이 두 루트노드 위치에 저장돼 있는 원소수 혹은 높이를 비교합니다. 둘 중 작은 쪽의 루트노드에 해당하는 $S$의 값을 큰 쪽 루트노드의 인덱스를 가리키도록 바꿉니다. 이 모든 연산이 $O(1)$에 해당합니다.
path compression
path compression은 다음과 같이 모든 노드가 루트를 가리키도록 만드는 것입니다. $S$에 부모노드 인덱스 대신 루트노드를 저장하는 방식입니다. find 연산을 수행할 때 트리의 높이만큼 거슬러 올라가야 루트노드를 찾을 수 있는데, 이러한 비효율성을 완화해보자는 취지입니다. path compression을 한번 수행해 놓으면 루트노드를 찾는 find 연산의 계산복잡성을 확 낮출 수 있습니다.
이번 글에서는 디스조인트 셋(Disjoint Set)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아, 그리고 이곳을 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
디스조인트 셋이란 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조입니다. 디스조인트 셋은 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할(partition)하는 데 자주 쓰입니다. 이와 관련해 몇 가지 용어를 살펴보겠습니다.
- 셋(set)은 개체들의 집합입니다. (리스트 등과 달리 순서는 고려하지 않음)
- 셋 $A$의 모든 원소가 셋 $B$에 포함될 때 $A$를 $B$의 부분집합(subset)이라 합니다. 이 때 $B$는 $A$의 초월집합(superset)이라 합니다.
- 셋 $A$와 셋 $B$가 공유하는 원소가 하나도 없을 때 $A$와 $B$를 mutually disjoint하다고 합니다.
- 임의의 셋을 분할(partition)한다는 건 각 부분집합이 다음 두 가지 속성을 만족하는
디스조인트 셋이 되도록 셋을 쪼개는 걸 뜻한다. (1) 파티션된 부분집합을 합치면 원래의 셋이 된다. (2) 파티션된 부분집합끼리는 mutually disjoint, 즉 겹치는 원소가 없다.
예컨대 $S={1,2,3,4}$이고, $A={1,2}$, $B={3,4}$, $C={2,3,4}$, $D={4}$라면 $A$와 $B$는 $S$의 분할입니다. 이 때 $A$와 $B$가 디스조인트 셋입니다. 하지만 $A$와 $C$는 $S$의 분할이 아닙니다. 겹치는 원소가 있기 때문입니다. $A$와 $D$ 또한 $S$의 분할이 아닙니다. 둘을 합쳐도 $S$가 되지 않기 때문입니다.
operations
디스조인트 셋은 세 가지 연산이 있는데요. make-set은 초기화 연산이므로 union과 find가 핵심이라고 할 수 있겠습니다.
- make-set(x) : $x$를 유일한 원소로 하는 새로운 셋을 만듭니다.
- union(x, y) : $x$가 속한 셋과 $y$가 속한 셋을 합칩니다.
- find(x) : $x$가 속한 셋의 대표값(루트노드 값)을 반환합니다.
예를 들어 보겠습니다. $A={3,4}$인 디스조인트 셋이 이미 만들어져 있다고 칩시다. 이 경우 첫번째 들어간 원소인 3이 루트노드가 되며 3이 $A$를 대표하는 값이 됩니다. 다음과 같습니다.
find(4)는 4가 속한 셋의 대표값을 출력하라는 뜻입니다. 따라서 이 예에서는 3이 됩니다. 마찬가지로 find(3) 또한 출력 결과가 3입니다.
이번엔 다른 디스조인트 셋 $B={1,2}$가 있다고 치겠습니다. $B$의 대표값은 루트노드인 1입니다. $A$와 $B$를 합칠 때는 루트노드들끼리 이어줍니다. 다음과 같습니다.
새롭게 만든 디스조인트 셋의 루트노드는 1입니다. 따라서 예컨대 4가 속한 셋의 대표값을 출력하라는 $find(4)$를 수행하면 출력 결과가 1이 됩니다.
array로 구현
디스조인트 셋의 세 가지 기본연산을 배열(array)로 구현해보겠습니다. $A={3,4}$, $B={1,2}$ 이렇게 두 개 디스조인트 셋이 이미 만들어져 있다고 칩시다.
이를 배열로 구현하면 다음과 같습니다. $N$은 입력원소들을 가리킵니다. $S$는 입력원소가 루트노드인지 아닌지, 부모노드가 어떤 위치에 있는지 나타냅니다. 예컨대 3과 1은 루트노드이기 때문에 이들에 해당하는 $S$의 값이 0입니다. 4의 부모노드는 $N$의 첫번째 요소, 즉 3이라고 표시가 되어 있네요. 마찬가지로 2의 부모노드는 $N$의 세번째 요소, 즉 1입니다.
- $N=[3,4,1,2]$
- $S=[0, 1, 0, 3]$
union 연산을 하면 $S$가 다음과 같이 바뀝니다.
- $S=[0, 1, 1, 3]$
그렇다면 union(x,y) 연산의 계산 복잡성은 얼마나 될까요? 크게 세 가지 단계로 나눠 생각해볼 수 있습니다.
- $x$가 속한 디스조인트 셋을 찾아야 합니다 : find(x)
- $y$가 속한 셋을 찾아야 합니다 : find(y)
- 찾은 셋을 합칩니다.
그런데 생각해보면 find 연산의 계산복잡성은 디스조인트 셋의 원소 수가 $n$개일 때 $O(\log{n})$입니다. 부모노드를 반복적으로 역추적해 루트노드를 찾습니다. 예컨대 잎새노드에서 루트에 이르기까지 일렬로 3-4-5-2-1 이렇게 구성돼 있는 디스조인트 셋이 있다고 할 때 find(3)은 엣지를 트리의 높이만큼 네 번 거슬러 올라가야 루트인 1을 찾을 수가 있습니다. find 연산을 좀 더 효율적으로 수행하기 위한 방법이 바로 path compression인데 조금 있다가 다루겠습니다.
find 연산을 두 번 수행해 합칠 셋을 찾았다고 칩시다. 그러면 이제 이 두 셋을 합칠 차례입니다. 합치는 방법에는 union-by-size와 union-by-height가 있는데 바로 다음에서 다루겠습니다.
union
임의의 두 디스조인트 셋을 합칠 때는 원소수가 적은 셋을 많은 셋의 서브트리로 합치는 것이 효율적입니다(union-by-size). 마찬가지로 트리의 높이가 작은 셋을 큰 셋의 서브트리로 합쳐야 합니다(union-by-height). 다음 union 연산 때 반드시 find 연산을 수행해야 하는데 find 연산의 효율성을 높여주기 위해서입니다. 원소수와 트리의 높이는 비례하는 경향이 있고 find 연산의 계산복잡성은 이들에 매우 의존적입니다.
union-by-size와 union-by-height를 구현하는 것은 간단합니다. 배열 $S$의 루트노드 정보를 바꾸면 됩니다. 루트노드일 때 0을 넣었던 기존과 달리 다음과 같이 바꿉니다.
- union-by-size : $-$size of tree
- union-by-height : $-$height of tree
요컨대 find 연산에서 찾은 두 개 디스조인트 셋의 원소수 혹은 높이를 비교해서 더 큰 쪽으로 합쳐줍니다. 이렇게 하면 이후 find 연산을 조금 더 효율적으로 수행할 수 있습니다.
union-by-size와 union-by-height의 계산복잡성은 $O(1)$입니다. find 연산에서 이미 두 디스조인트 셋의 루트노드를 찾았기 때문에 $S$에서 이 두 루트노드 위치에 저장돼 있는 원소수 혹은 높이를 비교합니다. 둘 중 작은 쪽의 루트노드에 해당하는 $S$의 값을 큰 쪽 루트노드의 인덱스를 가리키도록 바꿉니다. 이 모든 연산이 $O(1)$에 해당합니다.
path compression
path compression은 다음과 같이 모든 노드가 루트를 가리키도록 만드는 것입니다. $S$에 부모노드 인덱스 대신 루트노드를 저장하는 방식입니다. find 연산을 수행할 때 트리의 높이만큼 거슬러 올라가야 루트노드를 찾을 수 있는데, 이러한 비효율성을 완화해보자는 취지입니다. path compression을 한번 수행해 놓으면 루트노드를 찾는 find 연산의 계산복잡성을 확 낮출 수 있습니다.
Comments