[알고리즘] Union-Find | 서로소 집합(Disjoint Set)의 개념부터 최적화까지
알고리즘 문제를 풀다 보면, 여러 원소가 '같은 집합에 속해 있는지'를 빠르게 확인하고, 또 '두 집합을 하나로 합쳐야' 하는 상황을 종종 마주친다. 처음에는 단순 배열이나 그래프 탐색으로 접근했지만, 데이터의 크기가 커질수록 비효율의 벽에 부딪히는 경험을 했다. 이 문제를 효과적으로 해결하기 위해 고안된 자료구조가 바로 서로소 집합(Disjoint Set) 이며, 이를 구현하는 알고리즘이 Union-Find 이다…