유니온 파인드 경로 분할
IT 위키
유니온 파인드 경로 분할(Union-Find with Path Splitting)은 병합-찾기 자료구조에서 Find 연산의 효율을 높이기 위한 경로 압축 기법 중 하나로, 루트 노드를 찾는 동안 경로 상의 각 노드를 그 부모의 부모로 연결하는 방식이다.
1 개요[편집 | 원본 편집]
경로 분할(path splitting)은 유니온 파인드에서 트리의 깊이를 줄이고 Find 연산을 빠르게 만들기 위한 최적화 기법이다. 경로 압축(path compression), 경로 반결합(path halving)과 함께 대표적인 세 가지 경로 평탄화 전략 중 하나로, 각 노드를 루트와 더 가까운 위치로 옮김으로써 다음 연산에서의 접근 시간을 줄인다. 이 방법은 특히 반복적인 Find 연산이 많은 경우에 전체 자료구조의 효율성을 향상시킨다.
2 원리[편집 | 원본 편집]
- Find 연산 도중, 루트 노드를 찾기 위해 탐색하는 각 노드에 대해, 해당 노드의 부모를 그 부모의 부모로 설정한다.
- 이 작업은 탐색 경로의 노드를 한 단계 위로 끌어올리는 효과를 가지며, 전체 트리의 평균 높이를 낮춘다.
- 경로 분할은 재귀나 반복적인 방식으로 구현될 수 있으며, 경로 압축과 달리 모든 중간 노드가 업데이트된다.
3 구현 예시[편집 | 원본 편집]
다음은 경로 분할을 사용하는 Find 연산의 반복적 구현 예시이다:
def find(x):
while parent[x] != x:
parent[x], x = parent[parent[x]], parent[x]
return x
위 코드는 x에서 루트까지 올라가는 과정에서 x의 부모를 x의 조부모로 갱신하는 방식이다. 이 과정은 트리의 깊이를 간접적으로 줄여주는 효과를 가진다.
4 경로 분할 vs 경로 압축[편집 | 원본 편집]
- 경로 압축은 탐색 후 경로상의 모든 노드를 루트에 직접 연결하는 반면, 경로 분할은 경로상의 각 노드를 그 부모의 부모로 설정한다.
- 경로 분할은 반복 구조에 적합하고 구현이 단순하며, 메모리 접근 패턴이 더 고르게 분산되는 장점이 있다.
- 경로 압축은 더 강력한 평탄화를 제공할 수 있으나, 재귀적 구현에 의존하는 경우가 많다.
5 시간 복잡도[편집 | 원본 편집]
경로 분할은 경로 압축, 경로 반결합과 마찬가지로 유니온 파인드 자료구조의 시간 복잡도를 O(α(n))으로 줄인다. 이때 α(n)은 아커만 함수의 역함수이며, 대부분의 실용적인 입력에 대해 상수에 가까운 시간 성능을 제공한다.
6 활용[편집 | 원본 편집]
- Kruskal 알고리즘과 같은 그래프 기반 알고리즘에서의 Find 연산 최적화
- 네트워크 연결성 확인
- 사이클 검출 및 군집화 문제 등 반복적인 집합 조회가 필요한 경우
7 같이 보기[편집 | 원본 편집]
8 참고 문헌[편집 | 원본 편집]
- Tarjan, R. E., & van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM, 31(2), 245–281.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
