[서울대학교 논자시 준비] 알고리즘 : chapter 8 집합의 처리

문병로 교수님의 '관계 중심의 사고법 쉽게 배우는 알고리즘 개정판'을 보고 작성합니다.

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

연결리스트를 이용해 집합을 처리하면 각 원소당 하나의 노드를 만들고 이들을 연결리스트로 연결한다.

각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두개의 포인터가 있습니다.

 

각 집합의 대표원소는 연결 리스트의 맨 앞에 있는 원소가 된다. 

각 집합은 tail이라는 변수를 갖고 있다.

 

상호배타적 집합의 관리를 위해 세가지 연산이 필요하다.

1. Make-Set(x) : 원소 x로만 구성된 집합을 만든다 - 상수시간이 든다

2. Find-Set(x) : 원소 x를 가진 집합을 알아낸다 - 역시 상수 시간이 든다. (정상수) 왜 상수 시간이 드냐면 Find-Set은 원소 x를 포함하고 있는 집합의 대표 노드를 리턴하는 연산이기 때문이다

3. Union(x, y) : 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다. 평균 O(logn)이 든다.

Weighted Union은 큰 집합에 작은 집합을 붙이는 것이다.

 

2. 트리를 이용한 집합의 처리

각 집합을 하나의 트리로 표현한다. 여기서는 자식 노드가 부모 노드를 가리키도록 한다. 부모 노드를 따라가다보면 대표 노드를 만나게 된다.

 

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

각 노드는 자신을 루트로 하는 서브 트리의 높이를 랭크로 저장한다. 루트 노드의 랭크가 해당 집합의 랭크가 된다. 랭크를 이용한 union에서는 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.

 

트리를 이용하면 make-set, find-set, union을 모두 평균 수행 시간이 O(1) 이 되도록 만들 수 있다.