알고리즘 문제풀이

서로소 집합 ( Disjoint Set Unit, DSU ) 이란 ? 공통 원소가 없는 상호베타적인 부분 집합들로 나눠 진 원소들에 대한 정보를 저장하고 조작하는 자료구조. DSU는 해당 원소가 같은 집합 내에 포함되어 있는지 빠르게 확인하기 위해서 사용되는 자료구조이다. 공통 원소를 포함하고 있지 않는 집합이므로, 교집합 or 차집합 등의 연산은 불필요하다.(= 의미가 없다) 핵심 연산( Union - Find ) Union 연산 : 2개의 DSU를 하나의 Set으로 합쳐주는 연산 Find 연산 : 어떤 element 가 주어 질 때, 이 Element가 속해있는 집합의 대표원소를 반환 *대표 원소가 같다 -> 같은 서로소 집합 에 속해 있다는 것. Disjoint Set은 Array, Linked L..