Union-Find 알고리즘이란
•
Disjoint Set 을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘
•
간단하게, 노드 들 중에 연결된 노드를 찾거나, 노드 들을 서로 연결할 때 (합칠 때) 사용
Disjoint Set이란
•
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
•
공통 원소가 없는 (서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미함
•
Disjoint Set = 서로소 집합 자료구조
예제로 이해하는 Union-Find 알고리즘
Union-Find 알고리즘의 고려할 점
•
Union 순서에 따라서, 최악의 경우 링크드 리스트와 같은 형태가 될 수 있음
•
이 때는 Find/Union시 계산량이 O(N)이 될 수 있으므로, 해당 문제를 해결하기 위해,
•
union-by-rank, path compression 기법을 사용함
