[Algorithm] Union-find

1. Union-find 'Union-find' 는 '합집합-찾기' 자료구조라 말하며, 서로소 부분집합들로 나뉜 원소들에 대한 정보/데이터를 저장하고 조작하는 자료 구조 중 하나이다. 여기서 '서로소 부분집합'은 부분집합끼리 겹치는 요소가 없는 부분집합을 말하는데 즉, 서로간 공통요소가 하나도 없는 상태의 부분집합을 말한다. 'Union-find' 는 'Disjoin-set(서로소 집합)' 또는 'merge-find set(병합-찾기 집합)' 으로 불리기도 한다.  다시 돌아와서 해당 자료구조는 두 가지의 유용한 연산을 제공하는 것이 특징이다. 바로 'find' 와 'union' 인데 각각 아래와 같은 연산을 수행한다.find : 어떤 요소가 주어지면 해당 요소가 속한 집합(서로소 집합)을 반환한다. 즉..

2024.08.22