쉽게 배우는 알고리즘 7장. 상호 배타적 집합의 처리.

Presentation on theme: "쉽게 배우는 알고리즘 7장. 상호 배타적 집합의 처리."— Presentation transcript:

1 쉽게 배우는 알고리즘 7장. 상호 배타적 집합의 처리

2 7장. 상호 배타적 집합의 처리 얼마 전 나는 학술회의 준비차 다윈을 읽었다.
읽으면서 그 동안 읽지 않기를 잘했다는 생각이 들었다. 다른 때 다윈을 읽었더라면 여전히 이해할 수 없었을 것이기 때문이다. ... 결국, 읽을 준비가 되었을 때 읽어야 한다는 것이다. -로저 생크

3 학습목표 연결 리스트를 이용한 상호배타적 집합의 처리 방법을 이해한다.
연결 리스트를 이용한 집합의 처리를 위한 연산들의 수행시간을 분석할 수 있도록 한다. 트리를 이용한 상호배타적 집합의 처리 방법을 이해한다. 트리를 이용한 집합의 처리를 위한 연산들의 수행시간을 기본적인 수준에서 분석할 수 있도록 한다.

4 Set의 처리 이 장에서는 disjoint set(배타적 집합) 만을 대상으로 한다 그러므로 교집합은 없다 지원할 연산
Make-Set(x): 원소 x로만 이루어진 집합을 만든다 Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다 Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합 Linked list를 이용하는 방법과 tree를 이용하는 방법이 있다

5 Linked List를 이용한 처리 같은 집합의 원소들은 하나의 linked list로 관리한다

6 하나의 원소로 이루어진 집합 a tail

7 Linked List로 된 두 집합 a b c tail tail d e f g h

8 합집합을 만드는 예 파란색은 변동이 생긴 간선들 (a) a b c tail tail d e f g h (b) tail d e

9 Weight을 고려한 Union Linked list로 된 두 집합을 합할 때 작은 집합을 큰 집합의 뒤에 붙인다
대표 원소를 가리키는 포인터 갱신 작업을 최소화하기 위한 것

10 수행시간 [정리 1] Linked list를 이용해 표현되는 배타적 집합들을 만들면서 Weight을 고려한 Union을 사용할 때, m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set이라면 이들의 총 수행시간은 O(m + n log n)이다.  

11 Tree를 이용한 처리 같은 집합의 원소들은 하나의 tree로 관리한다 tree의 root를 집합의 대표 원소로 삼는다
child가 parent를 가리킨다 tree의 root를 집합의 대표 원소로 삼는다

12 Tree를 이용한 집합 표현의 예 c b h a e d f g

13 두 집합의 합집합 c e + b h d f g a c = b h e a d f g

14 하나의 원소로 이루어진 집합 a

15 Tree를 이용한 집합 처리 알고리즘 Make-Set(x) ▷ 노드 x를 유일한 원소로 하는 집합을 만든다. {
        p[x] ← x ; } Union(x, y) ▷ 노드 x가 속한 집합과 노드 y가 속한 집합을 합친다         p[Find-Set(y)] ← Find-Set(x) ; Find-Set(x) ▷ 노드 x가 속한 집합을 알아낸다. 노드 x가 속한 트리의 루트 노드를 리턴한다.         if (x = p[x]) then return x ; else return Find-Set(p[x]) ;

16 연산의 효율을 높이는 방법 Rank를 이용한 Union Path compression
각 노드는 자신을 루트로 하는 subtree의 높이를 랭크Rank라는 이름으로 저장한다 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다 Path compression Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 준다

17 랭크를 이용한 Union의 예 2 2 1 c c e + = 1 1 1 h e b h d f b a d f a

18 랭크를 이용한 Union에서 랭크가 증가하는 예
3 2 2 c c e + = 2 1 1 1 h e b h d f b 1 a d f a g g

19 Path Compression의 예 c c Find-Set(g) b h b h e g a e a d f d f g

20 Rank를 이용한 Union과 Make-Set
Make-Set(x) {         p[x] ← x;         rank[x] ← 0; } Union(x, y)         x' ← Find-Set(x);         y' ← Find-Set(y);         if (rank[x'] > rank[y'])                 then p[y'] ← x' ;                 else {                         p[x'] ← y' ;                         if (rank[x'] = rank[y']) then rank[y'] ← rank[y'] + 1;                 }

21 Path Compression을 이용한 Find-Set
Find-Set(x) {         if (p[x] ≠ x) then p[x] ← Find-Set(p[x]);         return p[x]; }

22 log*n = min {k : log log … log n ≤ 1}
수행시간 [정리 5] Tree를 이용해 표현되는 Exclusive set에서 랭크를 이용한 Union과 경로압축을 이용한 Find-Set을 동시에 사용하면, m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set일 때 이들의 수행시간은 O(m log*n)이다.   log*n = min {k : log log … log n ≤ 1} k 사실상 linear time임

23 Thank you