제7장 상호 배타적 집합의 처리

(1)

http://academy.hanb.co.kr

쉽게 배우는 알고리즘

7장. 상호 배타적 집합의 처리 IT COOKBOOK IT COOKBOOK

7장. 상호 배타적 집합의 처리

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

(2)

3 -IT COOKBOOK IT COOKBOOK 한빛미디어㈜

학습목표

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

Set의 처리

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

• Linked list를 이용하는 방법과 Tree를 이용하는 방법이 있다.

(3)

숙명여대 멀티미디어과학과 5

-Linked List를 이용한 처리

• 같은 집합의 원소들을 하나의 linked list로 관리한다_. • Linked list의 맨 앞의 원소를 집합의 대표 원소로 삼는다. • 각 집합에는 마지막 원소를 가리키는 tail을 둔다. – tail 포인터는 두 집합을 union 할 때 유용함. • Make-Set(x) 연산 – 원소 x로만 이루어진 집합을 만든다. • Find-Set(x) – 원소 x가 포함된 집합을 알아낸다. – 원소 x가 가리키는 대표 노드를 리턴한다.

집합 연산

x tail

(4)

-• Union(x, y) 연산

– 원소 x가 속한 집합과 원소 y가 속한 집합을 합친다. – 방법

• Find-Set(x)와 Find-Set(y)를 이용하여 x와 y가 속한 집합의 대표 노드를 각각 알아낸다. • 두 집합 중 하나를 다른 집합의 뒤에 붙인다. – 주 집합의 tail이 부 집합의 대표 노드를 가리키게 한다. – 부 집합의 모든 노드의 대표 원소 포인터는 주 집합의 대표 노드를 가리키게 한다.

집합 연산

a b c tail d e f g h tail

Linked List로 된 두 집합의 예

(5)

숙명여대 멀티미디어과학과 9 -a b c d e f g h tail tail d e f g h tail a b c (a) (b)

합집합을 만드는 예

파란색은 변동이 생긴 간선들

Weight을 고려한 Union

• Linked list로 된 두 집합을 Union할 때 작은 집합을 큰 집합의 뒤에 붙인다.

– 대표 원소를 가리키는 포인터 갱신 작업을 최소화하기 위함

(6)

숙명여대 멀티미디어과학과 11 -수행시간 [정리 1] Linked list를 이용해 표현되는 배타적 집합들을 만들면서 Weight을 고려한 Union을 사용할 때,

m번의 Set, Union, Find-Set 중 n번이

Make-Set이라면 이들의 총 수행시간은 O(m + nlog

n)이다.

Tree를 이용한 처리

• 같은 집합의 원소들은 하나의 트리로 관리한다

– 보통의 트리와는 달리 child가 parent를 가리킨다.

(7)

숙명여대 멀티미디어과학과 13 -c a e h b d f g

Tree를 이용한 집합 표현의 예

c a h b e d f g c a h b e d f g

두 집합의 합집합

+

=

• 두 집합 중 한 집합의 루트가 다른 집합의 루트를 가리키게 함.

(8)

숙명여대 멀티미디어과학과 15 -a

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

Tree를 이용한 집합 처리 알고리즘

Make-Set(x) ▷ 노드 x를 유일한 원소로 하는 집합을 만든다. { p[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 returnx ;

else returnFind-Set(p[x]) ; }

(9)

-연산의 효율을 높이는 방법

• Rank를 이용한 Union – 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(Rank)라는 이름으로 저장한다 • 단 하나의 노드로 이루어진 집합 트리의 랭크는 0 • 루트 노드의 랭크가 그 집합의 랭크가 됨 – 두 집합을 합칠 때 효율을 위해 rank가 낮은 집합을 rank가 높은 집합에 붙인다. 랭크를 이용한 _{Union의 예} c a e h b d f 0 0 0 1 1 0 2 c a e h b d f 0 0 0 1 1 0 2

+

=

(10)

숙명여대 멀티미디어과학과 19 -• 두 집합의 랭크가 동일하면 합집합의 랭크가 증가할 수 있음 랭크를 이용한 Union에서 랭크가 증가하는 예 c a e h b d f 0 1 0 2 1 0 2 c a e h b d f 0 1 0 2 1 0 3

+

=

g 0 g 0 • Path compression – Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접root를 가리키도록 포인터를 바꾸어 준다. Î 트리의 높이를 줄일 수 있음. c a e h b d f g c a e h b d f g Find-Set(g) Path Compression의 예

(11)

숙명여대 멀티미디어과학과 21 -Make-Set(x) ▷ 노드 x를 유일한 원소로 하는 집합을 만든다. { p[x] ← x; rank[x] ← 0; } Union(x, y) ▷ 노드x가 속한 집합과 노드 y가 속한 집합을 합친다. { x' ← Find-Set(x); y' ← Find-Set(y); if(rank[x'] > rank[y']) thenp[y'] ← x' ; else{ p[x'] ← y' ;

if (rank[x'] = rank[y']) thenrank[y'] ← rank[y'] + 1; }

}

Rank를 이용한 Union과 Make-Set

Find-Set(x) ▷ 노드x가 속한 트리의 루트 노드를 리턴한다.

{

if(p[x] ≠ x)

thenp[x] ← Find-Set(p[x]); // path compression 실시

returnp[x];

}

(12)

-수행시간

[정리 5]

Tree를 이용해 표현되는 Exclusive set에서 랭크를 이용한 Union과 경로압축을 이용한 Find-Set을

동시에 사용하면_{, m번의 Make-Set, Union,} Find-Set 중 n번이 Make-Find-Set일 때 이들의 수행시간은 O(mlog*_n)이다.

k

log*n = min {k : loglog …logn ≤ 1}

사실상linear time임

IT COOKBOOK IT COOKBOOK