Disjoint Set & Union-Find

목차 Disjoint Set (서로소 집합, 분리 집합) - Time Complexity 구현 - MakeSet(n) - find(x) - union(x, y) 최적화 - Path Compression - Path Halving - Path Splitting - Union by Rank - Union by Size Disjoint Set (서로소 집합, 분리 집합) 원소들의 모임을 표현하는 자료구조로, 각각의 집합은 공통된 원소가 없다. 주로 서로 다른 원소들이 동일한 집합에 속하는지 여부를 판별하는데 사용된다. Time Complexity 경로 압축과 트리 깊이 제어를 하는 로직이 없다면 선형 구조와 같은 예시에서 하나의 작업이 최대 O(N)이 될 수 있다. 하지만, 최적화를 위한 로직을 적용했다면, ..

2023.07.02