[자료구조] 디스조인트-셋(Disjoint-Set) - 유니온 파인드

해당 글은 마이구미님의 글과 위키백과를 참고하며 스스로 공부한 내용을 정리한 것입니다. Disjoint-Set을 같이 공부해봅시다! Disjoint(서로소) Set(집합)는 많은 서로소 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다. 이러한 특징으로 인해 Disjoint Set은 파티션(partitioning) 문제에 주로 이용됩니다. Disjoint Set 자료구조에는 3가지의 중요한 연산이 존재합니다. 서로소 집합이란? 공통 원소가 없는 두 집합, 교집합이 공집합인 집합입니다. 연산 메이크 셋 (MakeSet): 말 그대로 특정 한 원소만을 가지는 집합(들)을 만드는 것입니다. 파인드 (Find): 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환 합니다. 일반적으로 해..

2020.12.24