Algorithms/Union Find

알고리즘을 풀다가 분리집합, union-find 관련 문제를 자주 접하여 관련 개념들을 정리하고자 글을 적게 되었다. 1. Union-Find와 Disjoint Set`Union-Find, Disjoint Set` 두 단어 모두 알고리즘을 풀다 보면 한 번씩 들어보게 되는 용어이다. 처음에는 '2개의 문제 유형이 다른가?' 하고 생각을 했는데 같은 문제로 보면 될 것 같다.정확히 말하면 그래프 탐색에 dfs, bfs 알고리즘을 사용하듯이, 분리집합에는 Union-Find 알고리즘을 사용한다.하지만 분리집합을 관리하기 위한 알고리즘으로 Union-Find 알고리즘이 효율이 매우 좋아 다른 알고리즘이 필요하지 않는다고 보면 될 것 같다. 그럼 간략하게나마 각 용어의 개념을 정리해보자. Disjoint Set..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. Preview 시간 복잡도: O(M*a(N)) M : 연산 갯수 a(N) : 경로 압축한 find()의 시간 복잡도 공간 복잡도: O(N) 참고 : https://dheldh77.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8%ED%8C%8C%EC%9D%B..