[자료구조] Union Find / Disjoint-Set 알고리즘 개념 및 최적화

  목  차

• Union-Find Algorithm
  • 기본 개념
• 최적화

 

 

---

 

  Union-Find Algorithm

 

  기본적으로 Union-Find는 자료구조이다. 하지만 이 자료구조를 지원하는 Union과 Find는 알고리즘이다.

  여러 노드가 서로 중복되지 않는 집합 여러 개로 나뉘어 있을 때, 각 집합을 대표하는 노드를 찾거나 두 집합을 합치는 연산을 하는 자료구조이다.

 

 

  기본 개념

 

1. Union: 두 개의 원소가 포함된 집합을 하나로 합친다.

2. Find: 주어진 원소가 속한 집합의 대표 노드를 반환한다.

 

 

---

 

  최적화

 

대표적인 최적화는 '경로압축' 인데, 바로 Find 연산을 수행할 때,  방문한 노드를 모두 그 집합의 대표 노드로 바꾸는 것이다.

여기에 'Rank' 시스템을 도입하면 시간 복잡도가 눈에 띄게 줄어드는데, 작은 집합을 큰 집합에 합치는 것이다.

이렇게 하면 트리의 높이가 낮아져서 Find와 Union 연산의 시간 복잡도가 줄어든다.