<union-find 알고리즘> 개인적인 정리

 

프로그래머스 - 표병합(level3)

에 사용하기 때문에 찾아본 개념

 

 

 

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

 

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

Union-Find(혹은 Disjoint Set)은 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조이다. 이 자료구조가 서로 다른 두 개의 집합을 병합하는 Union 연산과 집합의 원소가 어떠한 집합에 속해있는지 판단하는 Find 연산을 지원하기 때문에 Union-Find라는 이름이 붙게 되었다. 1964년 처음 고안되었다. 크러스컬 알고리즘에서 원소 간의 연결 여부를 판단하는 데에 사용한다.

 

 

• Find 연산은 하나의 원소가 어떤 집합에 속해있는지를 판단하는 연산을 말한다.
• Union 연산은 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집합 연산과 동치이다.
• �n은 모든 원소의 개수로 한다.