[알고리즘] 상호 배타적 집합의 처리

상호 배타적 집합의 처리

※ 교집합은 다루지 않는다.

• 지원할 연산

– Make-Set(x): 원소 x로만 이루어진 집합을 만든다

– Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다

– Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합

연결 리스트를 이용하는 방법과 트리를 이용하는 방법

 

연결리스트를 이용한 집합 처리

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

• 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다

 

Weight를 고려한 Union

• 연결 리스트로 된 두 집합을 합칠 때 작은 집합을 큰 집합의 뒤에 붙인다

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

 

[예시] 다음의 상호배타적 집합이 연결리스트로 완성되기까지의 연산 과정을 쓰시오. (Make-set, union, find-set 등 사용)

{a, e, f} , {h, i, g, b}

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

[증명]

 

Make-Set을 수행한 횟수만큼 한 개씩의 원소를 가지는 n개의 집합이 생겼을 것이다. Weight를 고려한 Union을 자유롭게 적용함으로써 임의의 원소 x에 대한 대표 포인터 갱신 횟수 m을 최대가 되게 할 때의 m은 어떤 값인가?

1) Make-Set 8번 

m = log2(8) = 3

 

[설명] 임의의 원소 x를 위 예시에서 h로 잡을 경우 최대 3회가 된다.

2) Make-Set 16번

m = log2(16) = 4

3) Make-Set 32번 

m = log2(16) = 5

4) Make-Set 64번

m = log2(16) = 6 

5) Make-Set 2^k번

m = log2(2^k) = k 

 

복잡도 분석

Make-Set : 상수 이내

Find-Set : 상수 이내

union : logn

n개의 원소에 union 적용 시 : nlogn

트리를 이용한 집합 처리

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

– 자식 노드가 부모 노드를 가리킨다

• 트리의 루트를 집합의 대표 원소로 삼는다

 

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]); 
}

[예시] 다음의 트리가 되기 위한 연산 과정을 쓰시오.

[풀이]

make-set(a), make-set(b), make-set(c), make-set(h)

union(c, b) -> union(c, h) -> union(b, a)

이 과정에서 union(b, a)의 경우, a가 속한 루트가 c로 변경된다. 만약 union(b, a)가 아닌 union(c, a)라고 할 경우 c의 자식 노드가 3개로 구성된다.

 

연산 효율 높이기(1) : 랭크를 이용한 union과 make-set

– 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크 Rank 라는 이름으로 저장한다

– 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다. 랭크가 같은 두 집합의 경우 랭크가 증가한다.

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']) 
		then p[y'] ← x' ; 
	else { 
		p[x'] ← y' ; 
		if (rank[x'] = rank[y']) then rank[y'] ← rank[y'] + 1; 
	} 
}

 

[정리] Tree를 이용해 표현되는 Exclusive set에서 랭크를 이용한 Union을 사용하면, m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set일 때 이들의 수행시간은 O(mlogn)이다.  

• 한번의 Make-Set의 수행시간은 상수이내이다.

• 임의의 노드의 랭크는 O(logn)이다.

• 한번의 Find-Set의 수행시간은 랭크, 즉 O(logn)이다.

• 한번의 Union의 수행시간은 O(logn)이다.

 

Make-Set을 수행한 횟수만큼 한 개씩의 원소를 가지는 n개의 집합이 생겼을 것이다. 랭크를 고려한 Union을 자유롭게 적용함으로써 모든 원소의 랭크 값 중 최대값 m이 가장 커지게 하라. m은 얼마인가?

1) Make-Set 8번

2) Make-Set 16번

3) Make-Set 32번

4) Make-Set 64번

6

5) Make-Set 2^K번

k

연산 효율 높이기(2) : 경로 압축

– Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾸어 준다

Find-Set(x) { # 노드 x가 포함된 트리의 루트를 리턴한다.
	if (p[x] ≠ x) then p[x] ← Find-Set(p[x]); 
	return p[x]; 
}

위 트리에서 Find-Set(g)를 하게 되면 if문에 걸려 g의 부모인 Find-Set(e)를 하게 된다. 그러면 다시 Find-Set(h) .. Find-Set(c)에서 if문에 해당되지 않고 c를 리턴한다. 

결국 p[g] = c 가 되고 p[e] = c, p[h] = c 가 된다.

 

[정리 5] 트리를 이용해 표현되는 배타적 집합에서 랭크를 이용한 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}

사실상 선형 시간이다.

 

 

 

자료참조 - 쉽게 배우는 알고리즘 · 관계 중심의 사고법 / 문병로