유니온-파인드

1. 개요[편집]

유니온-파인드 Union-Find (Disjoint-Set Union, DSU)
다른 이름	서로소 집합 자료구조 · 분리 집합
표현	배열 하나로 된 부모 포인터 숲
연산	find(x) · union(x,y) · connected(x,y)
두 최적화	랭크(크기) 합치기 + 경로 압축
복잡도	m 연산에 O(m α(n)) — 상각 (Tarjan, 1975)
단골 손님	크러스컬 MST · 퍼콜레이션 클러스터 · 연결요소 라벨링

배열 하나. 함수 두 개. 스무 줄. 그런데 이걸 정확히 분석하는 데 인류가 20년 걸렸고, 그 답에 아커만 함수가 나온다.

유니온-파인드(union-find, 서로소 집합 자료구조)는 서로 겹치지 않는 집합들의 모임을 관리하면서, 두 집합을 합치는 union 과 어떤 원소가 어느 집합에 속하는지 묻는 find 를 둘 다 사실상 상수 시간에 처리하는 자료구조다. 1964년 갤러와 피셔가 컴파일러의 등가 선언(EQUIVALENCE) 처리를 위해 제안했다.¹

구현은 배열 하나다. parent[i] 에 부모의 인덱스를 넣고, 자기 자신을 가리키면 루트로 본다. 집합 하나가 트리 하나, 전체가 숲이며, 집합의 이름은 그 트리의 루트다. find 는 루트까지 올라가고, union 은 한쪽 루트를 다른 쪽 루트에 붙인다. 딱 이게 전부다.

문제는 아무 생각 없이 붙이면 트리가 길게 늘어져 사슬이 되고, find 가 $O(n)$ 이 된다는 것. 그래서 두 가지 최적화가 붙는데, 둘 다 켰을 때의 비용이 역아커만 함수라는 괴상한 답으로 나오는 것이 이 자료구조가 알고리즘 수업의 명물이 된 이유다.

2. 소박한 구현과 그 함정[편집]

find(x):   while parent[x] != x: x = parent[x];  return x
union(a,b): ra, rb = find(a), find(b);  if ra != rb: parent[ra] = rb

여기까지가 “순진한 링크”다. 정확하지만 트리 모양을 통제하지 않는다. union(0,1), union(1,2), union(2,3), … 을 순서대로 넣으면 높이 $n-1$ 짜리 외줄 사슬이 만들어지고, 그 뒤 깊은 노드에 find 를 걸면 매번 $n$ 스텝을 탄다.

고칠 방법은 두 갈래이고, 놀랍게도 서로 직교한다.

2.1. 랭크(또는 크기) 합치기 — 트리를 안 자라게 한다[편집]

union 에서 어느 쪽을 어느 쪽에 붙일지를 고른다. 각 루트에 랭크(높이 상한)를 들고 다니며 낮은 쪽을 높은 쪽에 붙인다. 같으면 아무 쪽에 붙이고 랭크를 1 올린다.

랭크 $r$ 인 트리는 적어도 $2^r$ 개의 노드를 갖는다는 것이 귀납법으로 나오므로 높이가 $\log_2 n$ 을 절대 넘지 못한다. 크기 합치기(작은 트리를 큰 트리에 붙이기)도 같은 보장을 주고, 크기 정보는 그 자체로 쓸모가 많아 실무에서는 크기 쪽이 더 흔하다.

2.2. 경로 압축 — 밟은 길을 평평하게 만든다[편집]

find 가 루트를 찾아 올라간 뒤, 그 경로에 있던 모든 노드를 루트에 직접 매단다. 이번에 낸 비용으로 다음번을 싸게 만드는 전형적인 상각 기법이다.

find(x):
  root = x;  while parent[root] != root: root = parent[root]
  while parent[x] != root: nxt = parent[x]; parent[x] = root; x = nxt
  return root

두 번 훑는 것이 싫으면 경로 이등분(path halving: parent[x] = parent[parent[x]] 하고 한 칸 올라가기)이나 경로 분할(path splitting)을 쓴다. 한 번만 훑고도 점근 복잡도가 같으며, 재귀를 안 쓰므로 스택 폭발 걱정도 없다. 실전 코드에서는 이쪽이 더 자주 보인다.²

3. 네 가지 정책을 실제로 재 보면[편집]

말로 하면 다 좋아 보이니 숫자를 보자. $n$ 개 원소에 $m=2n$ 개의 무작위 union 을 같은 시퀀스로 흘려보내고, 연산당 평균 find 스텝(밟고 올라간 간선 수)과 최종 숲의 최대 높이를 잰다.

$n=128$, $m=256$, 시드 고정:

정책	평균 find 스텝	최대 트리 높이
순진한 링크	11.637	38
랭크 합치기만	1.125	3
경로 압축만	1.516	4
둘 다	0.828	2

한 줄짜리 최적화 하나가 평균 스텝을 열 배 줄인다. 그런데 진짜 이야기는 $n$ 을 키울 때 나온다. 시드 200개 앙상블에서 $n$ 을 32에서 2048로 64배 키우면,

• 둘 다 정책: 평균 find 스텝 $0.784 \to 0.872$ (+11%), 평균 최대 높이 $1.78 \to 2.37$. 사실상 안 움직인다.
• 순진한 정책: 평균 최대 높이가 $\langle h\rangle \approx 0.173\,n + 7.0$ 으로 $n$ 에 선형. 자료구조가 아니라 연결 리스트다.
• 한쪽만 켠 정책: $\langle h\rangle$ 가 배가마다 약 0.39씩 늘어나는 로그 증가. 이론의 $\log_2 n$ 상한과 정확히 같은 모양이다.

$\alpha(n)$ 이 상수라는 이론적 주장이 실측에서 “64배 키웠는데 11% 늘었다”로 나타난 것이다. 이게 이 자료구조가 국룰인 이유의 전부다.

3.1. 지표에 따라 순위가 뒤집힌다[편집]

재미있는 것은 한쪽만 켠 두 정책의 우열이 지표마다 다르다는 점이다. $n=2048$ 에서

지표	랭크 합치기만	경로 압축만
평균 find 스텝	1.422	2.017
최종 최대 높이	4.98	4.70

평균 스텝은 랭크가 이기고 최종 높이는 압축이 이긴다. 이유는 두 최적화가 손대는 대상이 다르기 때문이다. 랭크는 union 시점에 미래의 모든 경로를 짧게 유지하는 예방책이고, 경로 압축은 이미 밟은 경로만 사후적으로 고치는 사후처리다. 그래서 압축은 자주 조회되는 노드에 대해서는 아주 강력하지만, 한 번도 안 밟힌 가지는 손대지 않은 채로 남겨 둔다. 반대로 랭크는 모든 가지를 균일하게 낮게 유지하지만, 특정 노드를 반복 조회해도 더 좋아지지 않는다.

벤치마크 지표를 하나만 보면 결론이 뒤집힌다는 교훈으로 새겨 둘 만하다. 논문이 “평균 경로 길이”만 보고했는지 “최대 깊이”만 보고했는지에 따라 어느 최적화가 이기는지 달라진다.

3.2. 높이가 비싼 게 아니라, 깊은 노드를 물어보는 것이 비싸다[편집]

교과서적 최악 사례로 알려진 사슬 시퀀스 union(0,1), union(1,2), union(2,3), … 을 넣어 보면 더 이상한 것이 나온다. 순진한 정책과 경로 압축만 켠 정책 모두 최종 높이가 정확히 $n-1$ 인데, 연산당 평균 find 스텝은 0 이다.

이유는 김이 빠질 만큼 단순하다. union(k, k+1) 을 할 때 인자 $k$ 는 이미 자기 트리의 루트고 $k+1$ 은 아직 아무와도 안 합쳐진 홀몸이라, 두 find 모두 한 칸도 안 올라간다. 사슬은 만들어지지만 아무도 그 사슬을 타지 않는다. 경로 압축은 밟은 경로만 고치므로, 밟지 않은 사슬은 끝까지 그대로 남는다.

여기서 나오는 통찰이 이 자료구조를 이해하는 핵심이다. 높이 자체가 비용이 아니다. 비용은 “깊은 노드에 대해 find 를 부르는 사건”에서만 발생한다. 그래서 최악 사례를 만들려면 사슬을 만드는 것만으로 부족하고, 사슬을 만든 뒤 그 밑바닥을 반복해서 조회해야 한다. 경로 압축의 상각 분석이 “worst case per operation”이 아니라 ”$m$ 연산 전체의 합”으로만 의미를 갖는 것도 이 때문이다 — 최악 시퀀스는 개별 연산이 아니라 연산들의 조합으로 만들어진다.

4. 복잡도 — α 가 나오는 자리[편집]

이 자료구조의 분석사는 그 자체로 알고리즘 이론의 축소판이다.

정책	$m$ 연산 상각 비용	출처
순진한 링크	$O(mn)$	—
랭크(크기) 합치기만	$O(m\log n)$	높이 $\le\log_2 n$
경로 압축만	$O\!\big(n + m\log_{1+m/n} n\big)$	Tarjan & van Leeuwen (1984)
둘 다	$\Theta(m\,\alpha(m,n))$	Tarjan (1975)

$\alpha$ 는 아커만 함수의 역함수다. 아커만 함수는 원시재귀적이지 않은 함수의 표준 예시로, 값이 상상을 초월하게 빨리 커진다. 그 역함수이므로 $\alpha$ 는 상상을 초월하게 천천히 커진다 — 우주에 있는 원자 수를 원소로 넣어도 $\alpha(n)\le4$ 다.³ 실용 범위에서 상수라고 봐도 되고, 실제로 위 실측이 그렇게 나왔다.

두 가지를 더 알아 둘 만하다. 첫째, 이 $O(m\alpha)$ 는 상한이 아니라 타이트하다 — 하한도 $\Omega(m\alpha)$ 이므로 이보다 좋은 분석은 없다(Tarjan 1979). 둘째, 프레드먼과 삭스(1989)가 셀 프로브 모형에서 $\Omega(\alpha)$ 상각 하한을 보였다. 유니온-파인드는 자료구조 설계가 아니라 문제 자체의 난이도가 $\alpha$ 라는 뜻이다. “상수 시간이 아니라 굳이 $\alpha$ 인 이유”에 대한 답이고, 이 하한이 나오기 전까지 사람들은 더 좋은 자료구조를 찾고 있었다.

역사적으로는 호프크로프트와 울먼(1973)이 먼저 $O(m\log^* n)$ 을 얻었고, 2년 뒤 타잔이 $\alpha$ 로 조였다. $\log^*$ 도 이미 실용 상수인데 굳이 더 조인 것 — 알고리즘 이론이 하는 일이 대개 이렇다.

5. 왜 이 바닥에서 국룰인가[편집]

시뮬레이션·수치해석에서 유니온-파인드가 등장하는 자리는 전부 같은 구조를 갖는다. “이 둘이 같은 덩어리인가”를 수없이 묻고, 덩어리를 합치기만 하고 쪼개지는 않는다.

• 크러스컬 MST. 간선을 가중치 오름차순으로 보면서 “이미 연결됐나”를 판정한다. find 두 번이 곧 사이클 검사다. 자세한 것은 최소 신장 트리 참고. 여기서는 정렬이 $O(E\log E)$ 로 지배적이고 유니온-파인드는 사실상 공짜다.
• 퍼콜레이션 클러스터. 점유 확률 $p$ 를 0에서 1로 올리며 사이트·본드를 하나씩 켜는 뉴먼–지프 알고리즘이 정확히 유니온-파인드다. 루트에 클러스터 크기를 매달아 두면 최대 클러스터 크기를 $O(1)$ 에 갱신할 수 있어, 침투 문턱 $p_c$ 근처의 곡선을 한 번의 스윕으로 전부 얻는다. 격자를 매번 새로 라벨링하는 소박한 방법에 비해 자릿수 단위로 빠르다.
• 연결요소 라벨링 / 호센-코프만. 2차원 격자를 한 번만 훑으며 왼쪽·위 이웃의 라벨을 보고 새 라벨을 주거나 물려받고, 나중에 같은 클러스터로 밝혀지면 병합한다. 호센-코프만 알고리즘은 유니온-파인드의 격자 특화판이고, 메모리가 한 줄 분량이면 된다는 것이 장점이다. 이미지 분할의 고전 알고리즘도 같은 뼈대를 쓴다.
• 격자·메시의 영역 분해. 메시 생성 후 물리적으로 분리된 부분을 찾거나, 적응 격자 세분화에서 같은 레벨의 인접 블록을 묶거나, 다중물질 계산에서 물질 조각을 추적하는 데 전부 쓴다. 영역 분할법의 전처리로 연결성을 먼저 확인하는 것도 관행이다.
• 계층적 군집화 · HDBSCAN. MST 간선을 가중치 순으로 병합하면 그 병합 순서가 곧 단일연결 덴드로그램이다. 루트에 부분트리 크기를 달아 두면 “군집이 언제 몇 개가 되었나”를 덤으로 얻는다.
• 격자 볼츠만 방법·다상 유동의 기포 추적. 같은 상(phase)으로 표시된 셀을 묶어 기포·액적을 개체로 인식하고, 개수·부피·중심을 통계 낸다. 매 스텝 깊이 우선 탐색을 돌리는 것보다 증분 갱신이 압도적으로 싸다.

반대로 쪼개기가 필요한 순간 이 자료구조는 무력하다. union 은 되지만 split 은 안 된다 — 압축된 포인터를 되돌릴 방법이 없기 때문이다. 그게 다음 절의 주제다.

6. 되돌릴 수 있는 union 과 오프라인 동적 연결성[편집]

간선이 추가되기만 하는 것이 아니라 삭제도 되는 동적 연결성 문제는 훨씬 어렵다. 온라인으로 풀려면 홀름–데 리흐텐베르크–소프의 $O(\log^2 n)$ 자료구조나 오일러 투어 트리 같은 물건이 필요하다. 그런데 질의를 미리 다 알고 있다면(오프라인) 유니온-파인드로 충분하다.

핵심 도구가 롤백 가능 DSU 다. 만드는 법은 뺄셈이다 — 경로 압축을 끄고 랭크 합치기만 쓴다. 그러면 각 union 이 배열 두 칸(자식의 parent, 부모의 rank)만 바꾸므로, 바뀐 칸의 옛 값을 스택에 쌓아 두었다가 그대로 되돌릴 수 있다. 압축을 끈 대가로 연산당 비용이 $O(\log n)$ 으로 오르지만, $\alpha$ 와 $\log n$ 의 차이는 실전에서 대개 무시할 만하다.

이걸 시간축 세그먼트 트리 위에서 분할 정복하면 오프라인 동적 연결성이 된다. 각 간선이 “살아 있는 시간 구간”을 시간축 구간들에 배정하고, 세그먼트 트리를 깊이 우선 탐색으로 내려가며 진입할 때 union, 빠져나올 때 롤백한다. 간선 하나가 $O(\log T)$ 개 노드에 배정되므로 전체가 $O(m\log T\log n)$ 이다. 몬테카를로 시뮬레이션에서 “이 파라미터 구간에서만 이 연결이 존재한다”는 종류의 질문에 그대로 쓸 수 있는 패턴이다.

변형 하나 더. parent 포인터에 간선 가중치를 함께 저장하면(가중 DSU, 퍼텐셜 DSU) ”$x$ 와 $y$ 의 차이가 얼마인가” 같은 질의를 처리할 수 있다. $\mathbb Z_2$ 가중치면 이분성 판정(홀수 사이클 검출), 실수 가중치면 차분 제약 시스템의 일관성 검사가 된다. 경로 압축 시 가중치를 누적해서 갱신하면 되므로 코드는 몇 줄 안 늘어난다.

7. 병렬·락프리 DSU[편집]

GPU 컴퓨팅이나 대규모 병렬 컴퓨팅 환경에서 연결성분을 구할 때, 유니온-파인드를 그대로 병렬화하는 것은 생각보다 잘 된다.

• 락프리 DSU. parent 배열에 CAS(compare-and-swap)만 쓰면 락 없이 동시 union 이 가능하다. 각 union 이 하는 일이 “루트 한 칸의 값을 바꾸는 것”뿐이므로, CAS가 실패하면 루트를 다시 찾아 재시도하면 된다. 경로 압축도 안전하다 — 압축은 포인터를 조상 방향으로만 옮기므로, 경쟁 상태에서 갱신이 유실되어도 정확성은 깨지지 않고 성능만 손해다. 이 “실패해도 틀리지 않는” 성질이 락프리 구현을 유난히 쉽게 만든다.
• 후킹 + 포인터 점프. 실로아흐–비슈킨(1982)의 고전 PRAM 연결성분 알고리즘이 사실상 병렬 DSU다. 모든 정점이 동시에 이웃 중 더 작은 루트에 “후킹”하고, 그다음 모든 포인터를 동시에 점프시켜 압축한다. $O(\log n)$ 라운드에 끝나며, 오늘날 GPU 연결성분 커널의 뼈대가 여전히 이 구조다.
• 보루브카와의 궁합. 병렬 MST의 표준인 보루브카 알고리즘은 라운드마다 성분 축약이 필요한데, 그 축약이 정확히 DSU다. 라운드마다 성분 수가 절반 이하로 줄어드는 성질과 DSU의 상각 비용이 맞물려 전체가 $O(E\log V)$ 로 유지된다.
• 분산 환경의 함정. 노드가 여러 대에 흩어지면 find 가 네트워크 왕복이 되어 $\alpha$ 고 뭐고 의미가 없어진다. 이때는 지역 DSU를 각자 돌리고 경계 정보만 주기적으로 병합하는 계층 구조로 간다. 통신 횟수가 복잡도를 지배하는 순간 자료구조 이론은 은퇴한다는, 분산 컴퓨팅의 흔한 결말이다.

8. 구현 요령[편집]

• find 는 반복문으로 쓴다. 재귀 구현은 순진한 정책에서 사슬을 만나면 스택을 넘긴다. 위 실측의 순진한 정책이 $n=2048$ 에서 평균 높이 360 수준이었다는 것을 상기하자.
• 랭크는 압축 후에도 갱신하지 않는다. 경로 압축이 실제 높이를 줄여도 랭크는 그대로 두는데, 그래도 상한으로서 유효하므로 분석이 깨지지 않는다. 랭크를 정확한 높이로 유지하려는 시도는 비용만 늘고 얻는 게 없다.
• 랭크보다 크기가 실용적이다. 크기는 루트에 매달린 부가 정보로도 쓸모가 많고(클러스터 크기 통계가 공짜다), 랭크와 성능 차이는 측정 오차 수준이다.
• 렘(Rem)의 알고리즘도 후보다. 두 경로를 번갈아 올라가며 그 자리에서 접합(splicing)하는 방식으로, 여러 실험 연구에서 경로 분할과 결합한 렘 알고리즘이 고전 조합보다 빨랐다고 보고된다. 캐시 지역성이 좋기 때문으로 설명된다.
• 인덱스를 정수로 압축해 두라. 실제 사고의 절반은 알고리즘이 아니라 “노드 id가 문자열이라 매 find 마다 해시 조회를 한다”에서 난다. 전처리로 $0\dots n-1$ 로 사상해 두면 배열 접근만 남는다.

9. 관련 문서[편집]

• 최소 신장 트리 · 그리디 알고리즘 · 동적 계획법
• 퍼콜레이션 · 호센-코프만 알고리즘 · 무작위 그래프
• 깊이 우선 탐색 · 너비 우선 탐색 · 강한 연결 요소 · 위상 정렬
• 계층적 군집화 · HDBSCAN · 이미지 분할
• 메시 생성 · 적응 격자 세분화 · 영역 분할법
• 병렬 컴퓨팅 · GPU 컴퓨팅 · 아커만 함수 · 세그먼트 트리

10. Footnotes[편집]

1. Galler, B. A. & Fischer, M. J. (1964). “An improved equivalence algorithm.” CACM 7(5). 포트란의 EQUIVALENCE 문(여러 변수를 같은 메모리에 겹쳐 두는 그 악명 높은 기능)을 컴파일러가 처리하려면 “어느 변수들이 같은 저장소를 공유하는가”를 관리해야 했고, 거기서 이 자료구조가 나왔다. 오늘날 물리 시뮬레이션과 그래프 알고리즘의 필수품이 된 물건의 출생지가 1960년대 컴파일러 백엔드라는 사실은 알아 둘 만하다. ↩

2. 경로 압축을 재귀로 쓰면 return parent[x] = find(parent[x]) 한 줄이라 예쁘다. 그런데 최적화가 안 켜진 초기 상태에서 사슬을 만나면 스택 깊이가 곧 트리 높이라서, $n$ 이 백만인 격자 퍼콜레이션 코드가 스택 오버플로로 죽는 사고가 실제로 자주 난다. 예쁜 코드가 새벽 세 시에 사람을 부르는 전형적인 사례. ↩

3. $\alpha(n)\le4$ 가 성립하는 범위가 $n < A(4,4)$ 인데, $A(4,4)$ 는 $2^{2^{2^{65536}}}$ 보다 큰 수다. 지수 탑이 세 층이라는 말인데, 우주의 원자 수 $10^{80}$ 은 이 수 앞에서 반올림 오차도 못 된다. “실용 범위에서 4 이하”라는 표현은 겸손한 것이고, 정직하게는 “이 은하가 끝날 때까지 4 이하”가 맞다. ↩