0Pricing
Coding Interview Prep · 강의

경로 압축을 적용한 DSU

경로상의 모든 노드가 루트를 직접 가리키도록 경로 압축을 적용한 find를 구현해, 상각 find 시간이 거의 O(1)이 되도록 합니다.

경로 압축을 적용한 DSU은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

서로소 집합 결합이란 무엇인가요

서로소 집합 결합(DSU)은 유니온-파인드라고도 하며, 서로 겹치지 않는 집합들의 모음을 관리하는 자료 구조입니다. 두 가지 핵심 연산을 지원합니다. find는 원소 x가 어느 집합에 속하는지 확인하고, union은 x와 y를 포함하는 집합을 합칩니다. DSU는 그룹이 시간이 지나면서 합쳐지지만 분리되지는 않는 동적 연결성 문제에 적합합니다.

모든 원소는 처음에 자기 자신만의 집합으로 시작합니다. 간선이나 관계를 처리하면서 집합들을 서로 합칩니다. 문제는 이 작업을 효율적으로 수행하는 것입니다. 단순한 구현은 연산마다 O(n)이 걸리지만, 최적화를 적용하면 분할 상환 기준으로 O(1)에 가까워집니다.

# Naive DSU without optimisations
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # each node is its own parent

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

순진한 find의 문제

순진한 DSU에서는 find(x)가 자기 자신을 가리키는 노드(루트)에 도달할 때까지 부모 연결을 따라 위로 올라갑니다. 트리가 균형 잡혀 있다면 이는 O(log n)입니다. 하지만 항상 두 번째 루트를 첫 번째 루트 아래에 연결하는 방식으로 union하면 길이가 n인 연결 사슬(퇴화 트리)을 만들 수 있으며, 이 경우 각 find는 O(n)이 됩니다.

0→1→2→3→4를 순서대로 union한다고 가정해 보겠습니다. 노드 0의 find 호출은 연결 사슬 전체를 순회해야 합니다. 경로 압축을 사용하면 find 작업 중 방문한 모든 노드가 루트를 직접 가리키도록 만들어 이 문제를 해결할 수 있습니다.

# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4]  => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4]  => find(0) takes 1 step

parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
    x = parent[x]
    steps += 1
print('Root:', x, 'Steps taken:', steps)

경로 압축: 단일 패스 재귀 방식

경로 압축은 루트를 찾은 뒤 경로에 있는 모든 노드가 루트를 직접 가리키도록 find 작업을 수정합니다. 그러면 이후 해당 노드에서 수행하는 find 호출은 O(1)이 됩니다. 재귀 방식은 한 번의 순회로 이를 우아하게 구현합니다.

핵심은 재귀 호출이 루트를 반환한 뒤 반환하기 전에 self.parent[x] = root를 설정하는 것입니다. 이렇게 하면 트리가 평탄화됩니다. 검색 경로에 있는 모든 노드가 이제 루트를 직접 가리킵니다. 이 작업은 노드가 속한 집합을 바꾸지 않고, 이후 조회 경로만 짧게 만듭니다.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)

경로 압축: 두 번의 순회 반복 방식

경로 압축의 반복 방식은 두 번의 순회를 사용합니다. 첫 번째 순회에서는 루트를 찾기 위해 위로 올라가고, 두 번째 순회에서는 경로의 모든 노드를 다시 방문하여 부모가 루트를 직접 가리키도록 업데이트합니다. 이 방식은 재귀 호출 스택의 오버헤드를 피하며, Python의 재귀 한도에 가까운 매우 깊은 트리에서도 안전합니다.

재귀 방식과 반복 방식 모두에서 정확성은 변하지 않습니다. find는 여전히 같은 루트를 반환합니다. 유일한 차이는 부수 효과로 부모 포인터가 업데이트된다는 점이며, 그 결과 해당 노드에서 수행하는 이후의 모든 find가 O(1)이 됩니다.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]          # first pass: find root
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root             # second pass: compress
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
            return True
        return False  # already connected

dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
    dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after  find(0):', dsu.parent[:])

경로 압축의 상각 복잡도

경로 압축만 사용해도 m개의 작업으로 이루어진 연산 순서에서 연산당 상각 시간은 O(log n)이 됩니다. 연결 사슬을 처음 순회할 때는 각 find 연산에 큰 비용이 들 수 있지만, 해당 연결 사슬을 평탄화하므로 이후 그 노드에서 수행하는 find는 모두 O(1)이 됩니다. 전체 작업량이 여러 연산에 분산되는 것입니다.

형식적인 분석에는 퍼텐셜 함수 방법이 사용됩니다. 노드의 부모까지의 경로가 짧아질 때마다 DSU의 퍼텐셜이 감소하고, 이 감소분이 순회 비용을 충당합니다. 랭크 기준 union 없이 경로 압축만 사용하면 상각 시간은 O(log n)으로, 순진한 방식의 O(n)보다 이미 크게 향상됩니다.

# Demonstrating amortised benefit
import time

def build_chain(n):
    parent = list(range(n))
    for i in range(n - 1):
        parent[i] = i + 1  # chain: 0->1->2->...->n-1
    return parent

n = 1000
parent = build_chain(n)

# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
    root = parent[root]
# Compress
while parent[x] != root:
    nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0])  # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')

연결 요소 개수 세기

DSU의 일반적인 활용 사례는 그래프의 연결 요소를 세는 것입니다. components 카운터를 n(노드마다 하나)으로 초기화합니다. 서로 다른 두 집합을 합치는 성공적인 union이 수행될 때마다 카운터를 1씩 감소시킵니다. 마지막에는 카운터가 서로 다른 요소의 개수를 나타냅니다.

이는 연결성 질의에 BFS나 DFS를 실행하는 것보다 효율적이며, 특히 간선이 점진적으로 도착하는 경우(온라인)에 유리합니다. DSU는 간선이 언제 도착하든 각 간선을 거의 O(1)의 상각 시간으로 처리합니다.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        self.parent[px] = py
        self.components -= 1
        return True

dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
    dsu.union(u, v)
print('Components:', dsu.components)  # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')

그래프 문제를 위한 DSU: 지방의 수

지방의 수 문제에서는 n×n 인접 행렬이 주어지고, 직접 또는 간접적으로 연결된 도시 그룹이 몇 개인지 묻습니다. 이는 DSU가 깔끔하게 해결할 수 있는 연결 요소 문제입니다. isConnected[i][j] == 1인 모든 쌍 (i, j)을 순회하며 union(i, j)를 호출합니다.

모든 연결을 처리한 뒤 dsu.components가 정답입니다. 방문하지 않은 모든 노드에서 BFS를 실행하는 것보다 간단하고 빠르며, 먼저 인접 리스트를 만들지 않고도 행렬 표현을 직접 처리할 수 있습니다.

def find_provinces(isConnected):
    n = len(isConnected)
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False

    count = n
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                if union(i, j):
                    count -= 1
    return count

matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix))  # 2: cities {0,1} and {2}

경로 압축 변형: 절반 단축

두 번의 순회를 사용하는 압축 방식 외에도 경로 절반 단축이라는 더 간단한 단일 패스 변형이 있습니다. 연결 사슬을 따라 올라가면서 각 노드가 부모 대신 조부모를 가리키도록 만듭니다. 이렇게 하면 두 번째 순회 없이 각 순회마다 경로 길이가 절반으로 줄어들며, 랭크 기준 union과 함께 사용할 경우 동일한 O(alpha(n)) 상각 복잡도를 달성합니다.

경로 절반 단축은 재귀나 두 번째 순회 없이 하나의 깔끔한 반복문으로 구현되므로 경쟁 프로그래밍에서 자주 선호됩니다. 각 단계에서는 self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x]를 실행합니다.

class DSUHalving:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # point to grandparent
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
    dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))

union 후 연결성 확인

두 노드가 연결되어 있는지(같은 요소에 속하는지) 확인하려면 find(x) == find(y)를 호출합니다. 두 호출이 같은 루트를 반환하면 두 노드는 같은 요소에 속합니다. 이것이 connected 질의이며, 경로 압축을 사용하면 상각 시간이 거의 O(1)입니다.

면접 문제에서는 연결성 질의가 union 연산과 섞여서 자주 등장합니다. DSU는 이 두 작업을 모두 온라인으로 처리하므로, 어떤 순서로든 union과 질의를 번갈아 수행할 수 있습니다. 이 점이 BFS/DFS 같은 정적 그래프 알고리즘과의 차이입니다. 정적 그래프 알고리즘은 구조가 변경될 때마다 다시 실행해야 합니다.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

    def connected(self, x, y):
        return self.find(x) == self.find(y)

dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7))   # True: 0-3-7
print(dsu.connected(0, 5))   # False: different components
print(dsu.connected(1, 5))   # True: 1-5

DSU 구현에서 흔히 발생하는 실수

자주 발생하는 실수는 find를 호출한 뒤 parent를 잘못 수정하는 것입니다. 같음을 확인하기 전에 항상 두 원소 모두에 대해 find를 호출해야 합니다. 그렇지 않으면 노드와 자신의 루트를 잘못 비교할 수 있습니다. 또 다른 실수는 두 원소가 이미 같은 루트를 공유할 때 union이 아무 작업도 하지 않아야 한다는 점을 잊는 것입니다.

Python에서는 재귀 깊이 한도(기본값 1000) 때문에 재귀 방식의 find가 큰 연결 사슬에서 RecursionError를 일으킬 수 있습니다. 반복 방식의 두 번 순회 버전을 사용하거나, sys.setrecursionlimit으로 한도를 늘리거나, 반복 방식의 경로 절반 단축을 사용하여 깊은 재귀 자체를 피해야 합니다.

import sys
sys.setrecursionlimit(10000)  # needed for large recursive DSU

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        # Safe iterative path compression
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already same component — do nothing
        self.parent[px] = py
        return True

dsu = DSU(5)
print(dsu.union(0, 1))  # True: merged
print(dsu.union(0, 1))  # False: already merged — no double-counting

DSU의 크기 추적

일부 문제에서는 루트뿐 아니라 각 요소의 크기가 필요합니다. 모든 값을 1로 초기화한 size 배열을 추가합니다. 두 요소를 합칠 때는 더 작은 루트의 크기를 더 큰 루트에 더합니다. 이렇게 하면 union 이후 요소 크기를 O(1)에 조회할 수 있습니다.

크기 추적은 크기 기준 union의 기반이기도 합니다. 이는 랭크 기준 union의 대안으로, 항상 작은 트리를 큰 트리의 루트 아래에 연결합니다. 이 방식은 트리 높이를 O(log n)으로 유지하므로 랭크 기준 union과 동일한 점근적 보장을 제공합니다.

class DSUWithSize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            px, py = py, px           # attach smaller under larger
        self.parent[py] = px
        self.size[px] += self.size[py]

    def get_size(self, x):
        return self.size[self.find(x)]

dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
    dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0))  # 3
print('Size of component containing 3:', dsu.get_size(3))  # 2
print('Size of component containing 5:', dsu.get_size(5))  # 1

빠른 확인

이번 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 테스트해 보세요.

레슨 요약

이번 레슨에서는 DSU가 find와 union 연산으로 서로소 집합을 유지한다는 것, 경로 압축이 순회한 모든 노드가 루트를 직접 가리키도록 하여 트리를 평탄화한다는 것, 그리고 이를 통해 find의 상각 성능이 거의 O(1)이 된다는 것을 배웠습니다. 다음으로는 트리를 위에서부터 아래로 얕게 유지하여 역 아커만 한계를 달성하는 랭크 기준 union을 살펴보겠습니다.

자주 묻는 질문

“경로 압축을 적용한 DSU” 강의는 무료인가요?

네 — “경로 압축을 적용한 DSU” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“경로 압축을 적용한 DSU”에서 뭘 배우나요?

경로상의 모든 노드가 루트를 직접 가리키도록 경로 압축을 적용한 find를 구현해, 상각 find 시간이 거의 O(1)이 되도록 합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

“경로 압축을 적용한 DSU” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 경로 압축을 적용한 DSU
  2. 랭크에 의한 합치기와 역 아커만 상한
  3. 중복 간선과 사이클 탐지
  4. 계정 병합과 연결 요소
← Coding Interview Prep(으)로 돌아가기