가정: 상호배타적 집합만을 대상으로 하기에 교집합은 없다
Make-Set(x): 원소 x로만 이루어진 집합을 생성
Find-Set(x): 원소 x를 가지고 있는 집합을 알아냄
Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합
표현방법 : 연결리스트, 트리
1) 연결 리스트
-같은 집합의 원소들은 하나의 연결 리스트로 관리
-연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼음
[정리 1]
연결 리스트를 이용해 표현되는 배타적 집합에서 무게를 고려한 Union을 사용할 때,
m번의 Make-Set, Union, Find-Set 중
n번이 Make- Set이라면 이들의
총 수행 시간은 O(m + n log n)이다.
2)트리
-같은 집합의 원소들은 하나의 트리로 관리
-자식 노드가 부모 노드를 가리킨다
-집합의 대표원소: 루트
연산의 효율을 높이는 방법
① 랭크를 이용한 union
-각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크Rank라는 이름 으로 저장한다
-두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다
② 경로 압축
- Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리 키도록 포인터를 바꾸어 준다
'알고리즘' 카테고리의 다른 글
| 쉽게 배우는 알고리즘-02 연습문제 (2) | 2023.10.23 |
|---|---|
| 쉽게 배우는 알고리즘-09동적프로그래밍(~돌놓기) (1) | 2023.10.23 |
| 쉽게 배우는 알고리즘-06검색트 (1) | 2023.10.23 |
| 쉽게 배우는 알고리즘-05선택 알고리즘 (0) | 2023.10.23 |
| 쉽게 배우는 알고리즘-04정렬 (1) | 2023.10.23 |