0. 서로소 집합
서로소(상호배타) 집합은 서로 중복 포함된 원소가 없는 집합이다. 즉, 교집합이 없는 집합을 의미한다.
집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분하며 이를 대표자(representative)라 한다.
서로소 집합을 표현하는 방법
- 연결 리스트
- 트리 → 구현이 쉬움
서로소 집합 연산
- Make-Set(x) - 유일한 멤버 x를 포함하는 새로운 집합을 생성 (서로소 집합 초기화 작업)
- Find-Set(x) - x를 포함하는 집합을 찾는 연산 (대표자 탐색)
- Union(x, y) - x와 y를 포함하는 두 집합을 통합하는 연산
1. 서로소 집합 표현
1-1. 연결 리스트
같은 집합의 원소들은 하나의 연결 리스트로 관리한다.
연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.
1-2. 트리
같은 집합의 원소들을 하나의 트리로 표현한다.
자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.
2. 구현
트리 구조를 이용해 서로소 집합을 구현한다.
3. 최적화
트리 구조를 만들다보면 아래와 같이 트리가 한쪽으로 편향되는 경우가 생길 수 있다.
이 경우 Find-Set의 시간 복잡도는 O(N)이 된다.
이를 해결하기 위한 방법으로 2가지를 제시할 수 있다.
3-1. 효율을 높이는 방법
- Rank를 이용한 Union
- 각 노드는 자신을 루트로 하는 subtree의 높이를 rank로 저장한다.
- 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.
- Path compression
- Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 준다.
3-2. 구현
반응형