서로소 집합
- 서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합 ( 교집합이 없다 )
- 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분 ( 대표자 )
- 서로소를 표현하는 방법
- 연결리스트
- 트리 ( 사용하기 가장 편함 → 많이들 사용함 )
- 서로소 집합 연산
- Make-Set(x) : 먼저 각각 자신만을 원소로 갖는 집합을 구성하는 Method
- Find-Set(x) : 해당 Parameter의 대표자를 찾는 Method
- Union-Set(x, y) : 해당 파라미터의 집합이 다를 경우에 두 집합을 합침
- → 같은 집합인지 확인하기 위해서 Find-Set(x), Find-Set(y)를 호출
서로소 집합 표현
- 연결 리스트
- 같은 집합의 원소들은 하나의 연결리스트로 관리
- 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 지정
- 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.
- 트리
- 하나의 집합을 하나의 트리로 표현
- 자식 노드가 부모 노드를 가리키고, 루트 노드가 대표자가 된다.
서로소 집합에 대한 연산
1. Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
2. Find-Set(x) : x를 포함하는 집합을 찾는 연산
3. Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산
Make-Set(x){
parents[x] = x
}
Find-Set(x){
if(parents[x] == x) RETURN x
else RETURN Find-Set(parents[x])
}
Union(x, y){
IF Find-Set(x) == Find-Set(y) RETURN
parents[Find-Set(y)] = Find-Set(x)
}
- 연산의 효율을 높이는 방법
- Rank를 이용한 Union
- 각 노드는 자신을 루트로 하는 서브 트리 높이를 Rank라는 이름으로 저장
- 두 집합을 합칠 때 Rank가 작은 집합을 Rank가 높은 집합에 붙임
- Path Compression
- Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꿔줌
- Rank를 이용한 Union
Path Compression 적용한 Find-Set 연산
- Find-Set(x) : x를 포함하는 집합을 찾는 오퍼레이션
// 수정 전
Find-Set(x){
if(parents[x] == x) RETURN x
else RETURN Find-Set(parents[x])
}
// 수정 후
Find-Set(x){
if(parents[x] == x) RETURN x
else RETURN parents[x] = Find-Set(parents[x])
}
- Find-Set 연산은 특정 노드에서 루트까지의 경로를 찾아 가면서 노드의 부모 정보를 갱신한다. → Find-Set(x)의 연산이 많아질수록 적은 시간으로 조회가 가능하다.
'Algorithms > 개념 정리' 카테고리의 다른 글
[문자열] 문자열 패턴 매칭 (0) | 2021.04.06 |
---|---|
[Graph] 최단 경로 (0) | 2021.03.30 |
[Graph] 최소 신장 트리(MST) (0) | 2021.03.29 |
[Graph] Graph 탐색 (0) | 2021.03.25 |
[Graph] Graph 이론 (0) | 2021.03.24 |