알고리즘/자료구조
2020. 5. 4.
유니온 파인드 (Union-Find)
유니온 파인드 (Union-Find Disjoint Set)은 교집합이 없는 서로소 집합들을 다루는 자료구조입니다. 유니온 파인드를 이용하면 서로소 집합들을 서로 합치거나(Union), 특정 원소가 어떤 집합에 속해있는지(Find) 알아내는 연산을 매우 효율적으로 할 수 있습니다. 유니온 파인드에서의 한 집합은 하나의 대표값(원소)로 표시하며, 그 집합에 포함된 다른 원소들은 대표원소로 가는 경로가 존재하는 트리 형태로 저장되게 됩니다. 예를 들어봅시다. 초기에 모든 원소들은 자기 자신을 대표원소로 가지는 크기 1인 집합에 속해 있습니다. $$\{1\},\{2\},\{3\},\{4\},\{5\},\{6\}$$ 여기에서 2번 집합과 3번 집합을 합치는 연산을 해봅시다. 합칠 때는 두 집합의 대표값중 하나를..
