분리 집합(유니온-파인드) (disjoint set (union-find))

한 줄 정의: 서로 겹치지 않는 여러 집합을 관리하면서, 두 원소가 같은 집합에 속하는지 확인(find)하고 두 집합을 하나로 합치는(union) 연산을 매우 효율적으로 지원하는 자료구조.

쉽게 풀면

유니온-파인드는 여러 개의 그룹으로 나뉜 원소들 중, 어떤 두 원소가 같은 그룹에 속하는지 빠르게 확인하고 두 그룹을 합치는 작업을 잘 처리하는 자료구조다. 각 그룹을 트리로 표현하고, 트리의 루트를 그 그룹의 대표로 삼는다. '경로 압축'과 '랭크에 의한 합치기'라는 두 가지 최적화 기법을 함께 사용하면 각 연산이 사실상 상수 시간에 가깝게 동작한다. 최소 신장 트리를 구하는 크루스칼 알고리즘이나 이미지에서 연결된 영역을 찾는 데 자주 쓰인다.

왜 중요한가

유니온-파인드는 그래프 알고리즘, 네트워크 연결성 분석, 이미지 처리, 클러스터링 등 '집합을 동적으로 합치며 소속 여부를 반복 확인'해야 하는 다양한 문제의 기반 자료구조이기 때문에 알고리즘 논문에서 자주 언급됩니다. 특히 최소 신장 트리, 퍼콜레이션 이론, 동적 연결성 문제를 다루는 연구에서 시간복잡도 개선의 핵심 도구로 인용됩니다. 거의 상수 시간에 가까운 연산 성능 덕분에 대규모 그래프를 다루는 실무 시스템에서도 표준적으로 채택됩니다.

논문에서는 이렇게 쓰입니다

"크루스칼 알고리즘 구현에서 경로 압축과 랭크 기반 합치기를 적용한 유니온-파인드 자료구조를 사용하여 사이클 검사를 거의 상수 시간에 수행하였다."

그래프에서 연결 요소를 관리하거나 클러스터링 결과를 병합할 때 사용하는 자료구조를 설명하는 데 쓰인다.

"이미지 분할 알고리즘에서 인접 픽셀 간 유사도를 기준으로 유니온-파인드를 적용해 연결된 영역을 빠르게 병합하였다."

컴퓨터 비전 분야에서 연결 성분 레이블링에 유니온-파인드를 활용하는 사례를 설명하는 표현이다.

"동적 네트워크에서 노드 추가에 따른 연결 요소 변화를 유니온-파인드 기반으로 실시간 추적하여 처리 지연을 최소화하였다."

네트워크 분석이나 시스템 설계 분야에서 동적 연결성 문제를 다룰 때 사용되는 표현이다.

조금 더 깊게 보면

유니온-파인드의 효율성은 두 최적화 기법의 조합에서 나옵니다. '경로 압축(path compression)'은 find 연산 중 방문한 노드들을 루트에 직접 연결해 트리 높이를 낮추고, '랭크(또는 크기) 기반 합치기'는 작은 트리를 큰 트리 아래에 붙여 트리가 한쪽으로 치우쳐 깊어지는 것을 막습니다. 두 기법을 함께 쓰면 연산당 평균 시간복잡도가 역 아커만 함수(inverse Ackermann function)에 비례하는 매우 느리게 증가하는 값이 되어 실질적으로 상수 시간으로 취급됩니다. 논문에서 성능을 논할 때는 이 이론적 시간복잡도와 실제 벤치마크 결과를 함께 제시하는 경우가 많습니다.

주의할 점

경로 압축이나 랭크 기반 합치기 같은 최적화를 적용하지 않으면 최악의 경우 연산 비용이 선형 시간까지 늘어날 수 있다.