프로그래머스 - 표병합(level3)
에 사용하기 때문에 찾아본 개념
https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html
[알고리즘] Union-Find 알고리즘 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
Union-Find(혹은 Disjoint Set)은 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조이다. 이 자료구조가 서로 다른 두 개의 집합을 병합하는 Union 연산과 집합의 원소가 어떠한 집합에 속해있는지 판단하는 Find 연산을 지원하기 때문에 Union-Find라는 이름이 붙게 되었다. 1964년 처음 고안되었다. 크러스컬 알고리즘에서 원소 간의 연결 여부를 판단하는 데에 사용한다.
-
Find 연산은 하나의 원소가 어떤 집합에 속해있는지를 판단하는 연산을 말한다.
-
Union 연산은 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집합 연산과 동치이다.
-
�은 모든 원소의 개수로 한다.
'알고리즘 > 알고리즘 정리' 카테고리의 다른 글
| <힙과 우선순위 큐> 개인적 정리 (0) | 2023.02.14 |
|---|---|
| <그래프 알고리즘 BFS, DFS, 델타함수> 개인적인 정리 (0) | 2023.02.14 |
| union_find, return 없는 def, global 배울점 많은 코드 (0) | 2023.02.14 |
| 이중 리스트 다루기(표로 사용시) (0) | 2023.02.11 |
| <이진 트리 구조> 참고 사이트 정리 (완전 이진 트리, 포화 이진 트리) (0) | 2023.02.10 |