블로그 이사 중입니다 >> gumgood.github.io

Disjoint-set 본문

Problem Solving/분류없음

Disjoint-set

gumgood 2017. 5. 27. 03:19

- Disjoint-set(분리집합) : 교집합이 존재하지 않는 두 집합

- 서로 구분되어야 하는 data 집합을 다룰 때 유용하게 쓰인다.


1. 연산

  Init() : n개의 element가 각각의 집합에 포함되어 있도록 초기화

  Union() : 두 element x, y가 주어질 때, 이 둘이 속한 두 집합을 하나로 합친다.

  Find() : 어떤 element x가 주어질 때, 이 element가 속한 set의 root를 반환한다.


2. 구현

  Find()연산은 각 element의 대표값을 재귀적으로 갱신해나간다. (경로압축)


  C++11


3. 시간복잡도

  Find() (= Union())의 시간복잡도는 경로압축시 O(ack(n))이다.

  ack(n) :  Ackermann function으로, 거의 에 근사한다.


4. 문제

  문제를 보고 바로 파악하기는 어렵다. 많이 풀어봐야할 것 같다.

  Kruskal's algorithm에 쓰인다.

'Problem Solving > 분류없음' 카테고리의 다른 글

Longest Increasing Subsequence  (0) 2017.05.27
Segment Tree (구간 트리)  (0) 2017.05.27
Disjoint-set  (0) 2017.05.27
Diameter of tree  (0) 2017.05.27
Tree Traversal  (0) 2017.05.27
Treap  (0) 2017.05.27
0 Comments
댓글쓰기 폼