분리집합이란
분리집합(Disjoint set)은 원소들의 모임을 나타내는 자료구조로서, 주로 서로소 집합(Disjoint set)이라고도 합니다. 이 자료구조는 원소들을 서로 중복되지 않는 집합으로 나누는 데 사용됩니다. 각 집합은 그 자체로 하나의 그룹을 형성하며, 다른 집합과는 공통 원소가 존재하지 않습니다.
분리집합은 대표적으로 다음 두 가지 연산을 지원합니다:
- MakeSet(x): 원소 x를 자신만으로 구성된 새로운 집합으로 만듭니다.
- Union(x, y): 두 개의 원소 x와 y가 속한 집합을 하나로 합칩니다. 이때, 두 집합이 서로 겹치지 않아야 합니다. 즉, 합쳐진 집합은 하나의 큰 집합이 됩니다.
분리집합의 사용
분리집합은 주로 그래프 이론과 연결 요소, 서로소 집합 자료구조를 활용하는 알고리즘에서 유용하게 사용됩니다. 예를 들어, 최소 신장 트리(Minimum Spanning Tree)를 구하는 크루스칼 알고리즘에서 사용되며, 그래프 내에서 사이클 여부를 판별하는 데에도 유용합니다.
분리집합의 최적화
분리집합은 경로 압축(Path compression)라는 최적화 기법을 적용하여 효율적으로 구현할 수 있습니다.
경로 압축(Path compression)은 분리집합(Disjoint set) 자료구조의 연산 중 하나로, 특히 Find 연산에서 사용되는 최적화 기법입니다. Find 연산은 주어진 원소가 속한 집합을 찾는 연산으로, 해당 집합의 대표 원소(루트 노드)를 반환합니다.
경로 압축은 Find 연산이 실행될 때, 해당 원소를 집합의 루트 노드에 직접 연결함으로써 트리의 높이를 최소화하는 방법입니다. 일반적으로 분리집합은 각 집합을 트리 형태로 표현하는데, 이때 트리의 높이가 커지면 Find 연산의 시간 복잡도도 커집니다. 경로 압축을 적용하면 트리의 높이를 줄이는 효과가 있어 Find 연산의 성능을 개선할 수 있습니다.
경로 압축은 재귀적으로 Find 연산을 수행하면서 경로 상의 모든 노드들을 직접 루트 노드에 연결합니다. 이렇게 하면 특정 원소를 찾을 때마다 해당 원소의 루트 노드로 바로 이동할 수 있기 때문에, 다음에 같은 원소를 찾을 때 더 적은 시간이 소요됩니다.
시간 복잡도
이러한 최적화를 통해, 단순한 구현에서의 시간복잡도인 O(n)을 훨씬 줄여서 O(log n)까지 단축시킬 수 있습니다.
마치며
다음에는 자세하게 분리집합의 알고리즘 중 하나인 union-find에 대해서 설명하겠습니다.
읽어주셔서 감사합니다.
