유니온-파인드 (Union-Find)
쉽게 풀면
여러 개의 친구 무리가 있다고 생각해 보세요. "철수와 영희가 같은 무리인가?"를 확인하는 게 find이고, "철수네 무리와 영희네 무리를 하나로 합친다"가 union입니다. 서로소 집합(disjoint set)이라고도 불리는 이 구조는 무리마다 대표(리더)를 한 명씩 정해두고, 두 사람이 같은 무리인지 확인할 때는 각자의 대표가 같은 사람인지만 비교하면 되도록 설계되어 있어 매우 빠릅니다.
왜 중요한가
유니온-파인드는 대규모 그래프에서 연결 관계를 매우 빠르게 관리할 수 있게 해주기 때문에, 네트워크 분석, 이미지 처리, 클러스터링 등 원소들을 그룹으로 묶고 그 관계를 반복적으로 갱신해야 하는 다양한 알고리즘 연구에서 기본 구성 요소로 채택됩니다. 특히 최소 신장 트리, 동적 연결성 문제처럼 그래프 구조가 계속 변화하는 상황을 효율적으로 다뤄야 하는 논문에서 자주 등장합니다.
논문에서는 이렇게 쓰입니다
이 문장은 수많은 노드와 간선으로 이루어진 네트워크에서, 어떤 두 노드가 서로 연결되어 있는지를 그래프 전체를 매번 탐색하지 않고도 거의 즉시 확인할 수 있었다는 뜻입니다. 최소 신장 트리를 구하는 크루스칼 알고리즘이나 이미지의 연결된 영역을 찾는 문제 등에서 핵심적으로 사용됩니다.
컴퓨터 비전 연구에서 이미지의 각 픽셀을 원소로 보고, 색이나 밝기가 비슷해 하나의 덩어리로 묶여야 할 픽셀들을 유니온-파인드로 빠르게 그룹화했다는 의미입니다.
소셜 네트워크 분석 논문에서, 본격적인 커뮤니티 탐지 알고리즘을 적용하기 전에 서로 연결된 사용자 그룹을 유니온-파인드로 미리 나눠 계산량을 줄였다는 뜻입니다.
조금 더 깊게 보면
유니온-파인드의 성능은 흔히 두 가지 최적화 기법에 의해 좌우되는데, 하나는 트리의 깊이를 얕게 유지하는 랭크(또는 크기) 기준 합치기이고 다른 하나는 find 연산 중에 거쳐 간 노드들을 대표 노드에 직접 연결해버리는 경로 압축입니다. 이 두 기법을 함께 적용하면 연산당 시간 복잡도가 사실상 상수에 가까운 매우 느리게 증가하는 함수(역 아커만 함수)로 표현될 만큼 효율적이라는 것이 이론적으로 알려져 있습니다. 다만 이 결과는 개별 연산이 아니라 여러 번의 연산 전체를 두고 평균을 낸 상각 시간 복잡도라는 점에 유의해야 합니다.
주의할 점
흔히 "거의 O(1)"이라고 표현하지만 이는 매 연산이 항상 상수 시간이라는 뜻이 아니라, 경로 압축 등의 최적화를 적용했을 때 여러 번의 연산을 전체적으로 평균 내면 연산당 비용이 극히 작아진다는 상각 분석 결과입니다. 단일 연산 하나만 떼어서 보면 여전히 그보다 느릴 수 있습니다.