유니온 파인드의 경로 압축과 크기 가중치: α(n)은 어떤 구현에 붙는 숫자인가
유니온 파인드에서 크기 가중치, 경로 압축, 경로 절반이 parent 배열을 각각 어떻게 바꾸는지 작은 예로 따라가고, 최악 Θ(log n)과 연산 열 전체의 O(m α(n))이 어느 구현에 해당하는지 Princeton algs4 자료를 기준으로 정리했습니다.
유니온 파인드(서로소 집합)의 복잡도는 흔히 “거의 O(1)”, “연산당 O(α(n))“으로 소개됩니다. 그런데 이 말이 성립하려면 조건이 붙습니다. 크기(또는 랭크) 가중치와 경로 압축을 함께 쓰는 구현이어야 하고, 대상은 연산 하나가 아니라 빈 상태에서 시작한 연산 열 전체입니다. Sedgewick·Wayne의 『Algorithms, 4th Edition』 공식 사이트(algs4)에 있는 구현 문서를 보면, 둘을 함께 쓴 구현도 union과 find 하나는 최악의 경우 Θ(log n) 시간이 걸린다고 적혀 있습니다.
아래에서는 algs4의 네 구현을 기준으로, 각 기법이 parent 배열을 어떻게 바꾸고 어떤 복잡도 문장이 어느 구현에 붙는지 나눠 봅니다.
parent 배열과 find
quick-union 계열 구현은 원소마다 parent[i]에 같은 집합 안의 다른 원소(또는 자기 자신)를 적어 둡니다. parent[i] == i인 원소가 루트이고, find는 링크를 따라 루트까지 올라갑니다. 두 원소의 루트가 같으면 같은 집합입니다. union은 두 루트를 찾은 뒤 한 루트를 다른 루트 아래에 붙입니다.
그래서 find의 비용은 출발한 노드의 깊이에 달려 있습니다. algs4 1.5절은 비용을 배열 접근 횟수로 세는데, quick-union의 find는 1 더하기 노드 깊이의 두 배만큼 배열에 접근한다는 명제를 둡니다. 나머지 기법은 모두 이 깊이를 줄이는 방법입니다.
크기 가중치: 작은 트리를 큰 트리 아래에
가중치 없는 quick-union은 어느 루트를 어느 쪽에 붙일지 고르지 않습니다. 원소 n개에 union(i, i+1)을 i = 0부터 차례로 부르면 algs4의 QuickUnionPathCompressionUF(id[rootP] = rootQ)는 0 → 1 → … → n−1로 이어지는 사슬을 만듭니다. 이 과정에서 find는 매번 루트에서 출발하므로 압축할 경로가 없고, 0의 깊이는 n−1이 됩니다.
WeightedQuickUnionUF는 트리마다 원소 수를 size[]에 기록하고, 작은 쪽 루트를 큰 쪽 루트 아래에 붙입니다.
if (size[rootP] < size[rootQ]) { parent[rootP] = rootQ; size[rootQ] += size[rootP]; }
else { parent[rootQ] = rootP; size[rootP] += size[rootQ]; }크기가 같으면 else 쪽으로 가서 q의 루트가 p의 루트 아래로 들어갑니다. 같은 union(i, i+1) 열을 이 구현에 넣으면 모든 원소가 0 바로 아래에 붙어 최대 깊이가 1입니다.
algs4는 가중 quick-union에 대해 원소 n개로 만든 숲에서 어떤 노드의 깊이도 lg n을 넘지 않는다는 명제와, 그 결과 find·connected·union의 최악 비용 증가 차수가 log n이라는 따름정리를 둡니다. 이 문장은 경로 압축이 없는 구현에 대한 것이고, 하나하나의 연산에 대한 최악의 경우입니다.
원소 8개(0~7)로 확인해 보겠습니다.
| 호출 | parent[0..7] | 바뀐 size |
|---|---|---|
| 처음 | 0 1 2 3 4 5 6 7 | 모두 1 |
| union(0,1) | 0 0 2 3 4 5 6 7 | size[0]=2 |
| union(2,3) | 0 0 2 2 4 5 6 7 | size[2]=2 |
| union(0,2) | 0 0 0 2 4 5 6 7 | size[0]=4 |
| union(4,5) | 0 0 0 2 4 4 6 7 | size[4]=2 |
| union(6,7) | 0 0 0 2 4 4 6 6 | size[6]=2 |
| union(4,6) | 0 0 0 2 4 4 4 6 | size[4]=4 |
| union(0,4) | 0 0 0 2 0 4 4 6 | size[0]=8 |
마지막 size 배열은 8 1 2 1 4 1 2 1입니다. 7에서 루트까지는 7 → 6 → 4 → 0으로 링크 3개, 정확히 lg 8입니다. 크기가 같은 트리끼리만 합쳤기 때문에 이 예는 상한에 딱 닿습니다. 이 일곱 번의 union에서 find는 모두 루트에서 출발했으므로, 경로 압축을 켠 구현으로 같은 호출을 해도 배열은 똑같습니다.
경로 압축: 지나간 노드를 루트에 직접 연결
algs4 1.5절은 모든 노드가 루트에 바로 연결되는 상태가 이상적이지만 많은 링크를 한꺼번에 바꾸는 비용은 치르고 싶지 않다고 하면서, find가 실제로 지나간 노드만 루트에 직접 연결하는 방법을 소개합니다. WeightedQuickUnionPathCompressionUF의 find는 두 번 훑습니다. 처음에는 루트를 찾고, 두 번째에는 경로의 노드를 하나씩 루트에 다시 연결합니다.
int root = p;
while (root != parent[root]) root = parent[root];
while (p != root) { int newp = parent[p]; parent[p] = root; p = newp; }
return root;위 상태에서 find(7)을 부르면 첫 번째 루프가 링크 3개를 따라가 루트 0을 찾고, 두 번째 루프가 7, 6, 4를 0에 직접 붙입니다.
| parent[0..7] | |
|---|---|
| find(7) 전 | 0 0 0 2 0 4 4 6 |
| find(7) 후(전체 압축) | 0 0 0 2 0 4 0 0 |
몇 가지를 짚어 둡니다.
- 이 find도 링크 3개를 따라갔습니다. 압축은 다음 find를 싸게 만들 뿐, 지금의 find를 줄이지 않습니다. algs4 문서가 이 구현에서도 union과 find를 최악의 경우 Θ(log n)으로 적는 이유가 여기서 보입니다.
- 루트는 바뀌지 않습니다. algs4 문서는 집합의 대표 원소가 union에서 집합이 바뀔 때만 바뀔 수 있고 find에서는 바뀌지 않는다고 적습니다. 압축은 트리 모양만 바꿉니다.
size[]는 갱신하지 않습니다. 압축 후 4 아래에는 5만 남았지만size[4]는 여전히 4입니다. 소스 주석에도 루트가 아닌 i의 size는 정확하지 않을 수 있다고 적혀 있습니다. union은size[rootP]와size[rootQ], 즉 루트의 값만 비교하므로 동작에는 문제가 없습니다. 압축은 원소를 다른 트리로 옮기지 않으니 루트의 size는 계속 그 집합의 원소 수입니다.
경로 절반: 한 번 훑으면서 할아버지로
1.5절에서 main()으로 동적 연결성 문제를 푸는 클래스 UF는 다른 조합을 씁니다. 크기 대신 랭크로 가중치를 두고, 경로 압축은 절반(halving) 방식입니다.
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;한 번 훑으면서 지나가는 노드를 할아버지에 연결하고, 다음에는 그 할아버지로 건너뜁니다. 그래서 경로에 있는 노드를 하나 걸러 하나씩만 고칩니다. 앞의 일곱 번 union을 UF에 넣으면 이 예에서는 모든 union이 같은 랭크끼리라 parent 배열이 크기 가중치 때와 같고, 랭크는 3 0 1 0 2 0 1 0이 됩니다. 여기서 find(7)을 부르면 결과가 다릅니다.
| parent[0..7] | |
|---|---|
| find(7) 전 | 0 0 0 2 0 4 4 6 |
| find(7) 후(경로 절반) | 0 0 0 2 0 4 4 4 |
7은 할아버지 4로 옮겨 가고, 4는 이미 할아버지가 0이므로 그대로이며, 6은 건너뛰어서 손대지 않습니다. 전체 압축처럼 한 번에 평평해지지는 않지만, find(7)을 한 번 더 부르면 7이 0으로 옮겨 갑니다. 대신 루트를 찾는 루프 하나로 끝나서, 1.5절 웹 연습문제는 경로 절반을 더 단순한 전략이라고 소개합니다.
어떤 문장이 어느 구현에 붙는가
아래 표는 algs4 소스의 클래스 문서와 1.5절 본문에 적힌 문장을 그대로 옮긴 것입니다.
| 구현 | 가중치 | 경로 압축 | 연산 하나(최악) | 연산 열 전체 |
|---|---|---|---|---|
WeightedQuickUnionUF |
크기 | 없음 | union·find Θ(log n). 깊이 ≤ lg n은 본문의 명제 | 따로 적지 않음 |
QuickUnionPathCompressionUF |
없음 | 전체 압축 | 적지 않음 | union·find·connected가 상각 로그 시간 |
WeightedQuickUnionPathCompressionUF |
크기 | 전체 압축 | union·find Θ(log n) | m번 연산에 O(m α(n)) |
UF |
랭크 | 경로 절반 | union·find Θ(log n) | m번 연산에 O(m α(n)) |
O(m α(n))의 정확한 조건은 이렇습니다. 원소 n개로 시작한 빈 자료구조에서 union과 find를 아무 순서로 섞어 m번 하면 총 O(m α(n)) 시간이 걸린다는 것이고, α(n)은 아커만 함수의 역함수입니다. 연산 하나당 α(n)이라는 말은 이 총합을 m으로 나눈 상각 비용입니다. 입력이 무작위라는 가정도 들어 있지 않습니다. 상각이라는 개념 자체가 낯설다면 동적 배열의 append가 O(1)인 이유에서 같은 방식의 계산을 볼 수 있습니다.
출처가 말하는 범위
이 수치들이 algs4 자료에서 어떤 형태로 나오는지도 구분해 둡니다.
- 깊이 ≤ lg n과 log n 최악 비용은 1.5절 본문의 명제와 따름정리입니다.
- 가중치 없는 경로 압축의 상각 비용이 로그라는 것과, 가중치와 경로 압축을 함께 쓸 때 상각 비용이 역아커만 함수로 묶인다는 것은 연습문제 1.5.12, 1.5.13에 붙은 참고(Note)로 “알려져 있다”고만 적혀 있습니다. 1.5.13의 참고는 현실에서 다룰 법한 어떤 n에서도 이 값이 5보다 작다고 덧붙입니다.
- O(m α(n))은
WeightedQuickUnionPathCompressionUF와UF의 클래스 문서에 있는 문장입니다.
이 글에서 연 자료에는 α(n) 상한의 증명이 없고, 원 논문도 확인하지 않았습니다. 그래서 랭크와 크기 중 어느 쪽이 나은지, 경로 절반과 전체 압축 중 어느 쪽이 실제로 빠른지 같은 비교는 하지 않았습니다. 위 표는 각 구현에 대해 algs4 문서가 적은 범위까지만 말합니다.
확인한 자료
모두 2026-10-18에 확인했습니다.