알고리즘 이론 공부 - 서로소 집합

About this offer

서로소 집합(Disjoint-set) 서로소 집합 은 서로 공통 원소가 없는 집합이다. 두 집합 A와 B가 서로소이면 교집합이 공집합이다. A ∩ B = ∅ 서로소 집합 자료구조는 여러 원소를 서로 겹치지 않는 집합들로 나누어 관리 한다. 각 원소는 하나의 집합에 속하며, 집합을 합치거나 두 원소가 같은 집합에 속하는지 확인할 수 있다. 집합에 속한 원소 하나를 대표자(Representative) 로 정해 집합을 구분한다. 대표자는 구현 규칙에 따라 결정되며 집합을 합치는 과정에서 바뀔 수 있다. {a, d, e} {b, f} {c} 대표 a 대표 b 대표 c 서로소 집합의 기본 연산 연산 역할 Make-Set(x) 원소 x만 포함하는 새로운 집합을 생성 Find-Set(x) x가 속한 집합의 대표자를 반환 Union(x, y) x와 y가 속한 두 집합을 하나로 합침 Find와 Union을 중심으로 사용하므로 Union-Find 라고도 부른다. 같은 집합인지 확인 원소 자체를 비교하는 대신 두 원소의 대표자가 같은지 비교한다. Find-Set(x) == Find-Set(y) → x와 y는 같은 집합에 속함 Find-Set(x) != Find-Set(y) → x와 y는 서로 다른 집합에 속함 집합을 합치는 예제 Union에서 첫 번째 집합의 대표자를 유지한다고 하자. 연산 집합 상태 또는 반환 값 Make-Set(x), Make-Set(y), Make-Set(a), Make-Set(b) {x}, {y}, {a}, {b} Union(x, y) {x, y}, {a}, {b} Union(a, b) {x, y}, {a, b} Find-Set(y) x Find-Set(b) a Union(x, a) {x, y, a, b} Union은 두 원소만 연결하는 연산이 아니라, 각 원소가 속한 집합 전체를 합치는 연산 이다. 이미 같은 집합에 속한다면 다시 합칠 필요가 없다. 연결 리스트를 이용한 표현 같은 집합의 원소들을 하나의 연결 리스트로 관리한다. 리스트의 맨 앞 원소를 대표자로 삼는다. 집합별로 대표자 rep 와 마지막 원소 tail 을 관리한다. 각 원소는 자신이 속한 집합의 대표자를 가리키는 링크를 갖는다. 대표 a 대표 b 대표 c ↓ ↓ ↓ a → d → e b → f c ↑ ↑ ↑ tail tail tail a, d, e의 대표자 링크 → a b, f의 대표자 링크 → b c의 대표자 링크 → c Find-Set 원소가 대표자를 직접 가리키므로 해당 링크를 읽으면 된다. Find-Set(e) → a Find-Set(f) → b 대표자 링크를 직접 저장하는 방식에서 Find-Set은 O(1) 이다. Union Union(a, b) 로 두 리스트를 합치면서 a를 대표자로 유지하는 과정은 다음과 같다. 첫 번째 리스트의 마지막 원소 e를 두 번째 리스트의 첫 원소 b에 연결한다. 두 번째 리스트에 있던 b와 f의 대표자 링크를 a로 변경한다. 합친 리스트의 마지막 원소를 f로 갱신한다. 합치기 전 a → d → e b → f c 합치기 후 a → d → e → b → f c a, d, e, b, f의 대표자 링크 → a 리스트를 이어 붙이는 것만으로는 충분하지 않다. 대표자가 바뀌는 원소들의 링크도 갱신 해야 한다. 따라서 붙이는 리스트의 원소 수가 k개라면 이 Union에 O(k)가 필요하다. 트리를 이용한 표현 같은 집합의 원소들을 하나의 트리로 표현한다. 각 노드는 자신의 부모를 가리킨다. 루트가 집합의 대표자이다. 루트는 자기 자신을 부모로 가리킨다. 여러 집합을 함께 표현하면 여러 트리로 이루어진 포리스트(Forest) 가 된다. 다음 그림은 위쪽 노드가 부모인 구조이다. 실제 부모 포인터는 자식에서 부모 방향을 가리킨다. a b c / \ | d e f parent[a] = a parent[d] = a parent[e] = a parent[b] = b parent[f] = b parent[c] = c Find-Set은 부모 포인터를 따라 루트에 도달할 때까지 이동한다. Union은 한 트리의 루트를 다른 트리의 루트 아래에 연결 한다. 트리 구성 예제 우선 a부터 f까지 각각 독립적인 집합을 만든다. {a}, {b}, {c}, {d}, {e}, {f} Union(c, d) 와 Union(e, f) 에서 각각 c와 e를 대표자로 유지하면 다음과 같다. a b c e | | d f 이후 Union(d, f) 를 수행한다. d의 대표자는 c, f의 대표자는 e이므로 e를 c 아래에 연결 한다. a b c / \ d e | f Find-Set(d) → c Find-Set(e) → c Find-Set(f) → f → e → c → 대표 c 반환 부모 배열에 저장 각 원소에 인덱스를 부여하고, 부모의 인덱스를 배열 p 에 저장한다. 인덱스 0 1 2 3 4 5 원소 a b c d e f 부모 인덱스 p 0 1 2 2 2 4 f의 인덱스는 5이므로 p[5] = 4 를 따라 e로 이동하고, p[4] = 2 를 따라 c로 이동한다. p[2] = 2 이므로 c가 루트이다. 부모와 대표자는 항상 같지는 않다. 위 구조에서 f의 부모는 e이지만 대표자는 c이다. 기본 연산 구현 원소 번호를 1부터 N까지 사용하고 0번 인덱스는 사용하지 않는다고 하자. Make-Set p[x] = x 로 설정하면 x가 자기 자신을 부모로 갖는 루트가 된다. N = 6 p = [0] * (N + 1) def make_set(x): p[x] = x for x in range(1, N + 1): make_set(x) print(p[1:]) 출력: [1, 2, 3, 4, 5, 6] Make-Set은 새로운 원소의 집합을 초기화할 때 사용한다. 이미 합쳐진 원소에 다시 적용하면 기존 집합 구조를 깨뜨릴 수 있다. Find-Set 자기 자신이 부모이면 루트이므로 바로 반환한다. 그렇지 않으면 부모에서 다시 Find-Set을 수행한다. def find_set(x): if x == p[x]: return x return find_set(p[x]) 이 구현은 루트를 찾기만 하며 부모 배열을 변경하지 않는다. Union 먼저 x와 y가 속한 집합의 루트 px , py 를 찾는다. 여기서는 번호가 작은 루트를 대표자로 유지 한다. def union(x, y): px = find_set(x) py = find_set(y) if px == py: return if px < py: p[py] = px else: p[px] = py 부모를 변경할 대상은 x나 y가 아니라 루트 px 또는 py이다. 일반 원소의 부모만 바꾸면 그 원소 아래의 일부만 이동하고, 원래 집합 전체가 합쳐지지 않을 수 있다. 작은 번호를 대표자로 삼는 규칙은 대표자를 선택하는 기준일 뿐, 트리 높이를 줄이는 규칙은 아니다. 부모 배열 연산 예제 앞의 기본 구현으로 다음 연산을 차례대로 수행한다. Make-Set(1)부터 Make-Set(6)까지 Union(1, 3) Union(2, 3) Union(5, 6) Find-Set(6) 연산 p[1] p[2] p[3] p[4] p[5] p[6] 집합 상태 초기화 1 2 3 4 5 6 {1}, {2}, {3}, {4}, {5}, {6} Union(1, 3) 1 2 1 4 5 6 {1, 3}, {2}, {4}, {5}, {6} Union(2, 3) 1 1 1 4 5 6 {1, 2, 3}, {4}, {5}, {6} Union(5, 6) 1 1 1 4 5 5 {1, 2, 3}, {4}, {5, 6} Find-Set(6) 1 1 1 4 5 5 대표자 5 반환, 배열 유지 Union(2, 3) 에서는 Find-Set(2) = 2 , Find-Set(3) = 1 이다. 따라서 루트 2의 부모를 1로 변경 한다. 앞의 초기화와 함수 정의를 실행한 뒤 다음 코드로 확인할 수 있다. union(1, 3) print(p[1:]) union(2, 3) print(p[1:]) union(5, 6) print(p[1:]) print(find_set(6)) print(find_set(2) == find_set(3)) print(find_set(1) == find_set(6)) 출력: [1, 2, 1, 4, 5, 6] [1, 1, 1, 4, 5, 6] [1, 1, 1, 4, 5, 5] 5 True False 기본 트리 구현의 문제점 Union에서 트리 높이를 고려하지 않으면 한쪽으로 긴 사슬이 만들어질 수 있다. 예를 들어 Union(f, e) , Union(e, d) , Union(d, c) , Union(c, b) , Union(b, a) 를 수행하면서 첫 번째 집합의 루트 아래에 두 번째 집합의 루트를 연결 하면 다음 구조가 된다. a → b → c → d → e → f 루트 화살표는 부모 방향이다. Find-Set(b) 는 다음 경로를 따라간다. b → c → d → e → f Find-Set의 비용은 트리 높이에 비례한다. N개 원소가 한 줄로 이어지면 한 번의 Find-Set에 최악 O(N) 이 필요하다. Union 역시 대표자를 찾는 과정이 필요하므로 긴 트리에서는 비용이 커진다. 루트끼리 연결하는 동작 자체는 O(1)이지만, 루트를 찾는 시간까지 포함 해야 한다. 경로 압축(Path Compression) 경로 압축은 Find-Set을 수행할 때 만난 노드들이 루트를 직접 부모로 가리키도록 변경 하는 방법이다. 같은 집합과 대표자를 유지하면서 트리 구조를 납작하게 만들어 이후 탐색 경로를 줄인다. 경로 압축 예제 다음 구조에서 Find-Set(h) 를 수행한다고 하자. 압축 전 a / \ b d | | c e /|\ f g h 탐색 경로: h → e → d → a 경로에 있는 h, e, d가 a를 직접 부모로 가리키도록 갱신한다. d는 원래도 부모가 a이므로 그대로이다. 압축 후 a ├── b │ └── c ├── d ├── e │ ├── f │ └── g └── h b와 c는 이번 탐색 경로에 없으므로 변경되지 않는다. f와 g의 부모도 여전히 e이다. 한 번의 Find-Set이 집합의 모든 노드를 압축하는 것은 아니다. 경로 압축 구현 재귀 호출이 루트를 반환하면 그 값을 현재 노드의 부모에 저장한다. def find_set(x): if x != p[x]: p[x] = find_set(p[x]) return p[x] 압축이 없는 구현은 find_set(p[x]) 의 결과를 바로 반환한다. 경로 압축 구현은 반환된 루트를 p[x]에 저장 한 뒤 반환한다. 부모 배열 변화 확인 다음은 a부터 h를 0부터 7까지의 인덱스로 표현한 독립적인 예제이다. labels = list("abcdefgh") p = [0, 0, 1, 0, 3, 4, 4, 4] print("압축 전:", p) root = find_set(7) print("대표자:", labels[root]) print("압축 후:", p) 출력: 압축 전: [0, 0, 1, 0, 3, 4, 4, 4] 대표자: a 압축 후: [0, 0, 1, 0, 0, 4, 4, 0] 경로 압축은 탐색이 끝난 뒤 구조를 개선한다. 처음 루트까지 올라가는 비용 자체가 사라지는 것은 아니다. Rank를 이용한 Union Rank 는 트리의 높이를 관리하기 위한 값이다. 처음에는 각 원소가 루트이고 높이가 0이므로 Rank를 0으로 초기화한다. Union에서는 Rank가 낮은 루트를 Rank가 높은 루트 아래에 연결 한다. 대표자의 번호보다 트리 구조를 우선해 긴 사슬이 만들어지는 것을 막는다. Rank가 서로 다른 경우 두 루트 a, e의 Rank가 각각 2와 1이라면 e를 a 아래에 연결한다. 합치기 전 a (Rank 2) e (Rank 1) / \ / \ b d f g | c 합치기 후 a (Rank 2) / | \ b d e (Rank 1) | / \ c f g 높이가 낮은 트리를 붙였으므로 새 루트 a의 Rank는 2로 유지 한다. Rank가 같은 경우 두 루트의 Rank가 모두 2라면 어느 루트를 새 대표자로 삼아도 된다. e를 a 아래에 붙인다고 하자. 합치기 전 a (Rank 2) e (Rank 2) / \ / \ b d f g | | c h 합치기 후 a (Rank 3) / | \ b d e (Rank 2) | / \ c f g | h 같은 높이의 트리를 붙이면 높이가 한 단계 증가하므로 새 루트의 Rank만 1 증가 시킨다. 두 루트의 Rank 연결 방법 새 루트의 Rank rank[px] > rank[py] py를 px 아래에 연결 유지 rank[px] < rank[py] px를 py 아래에 연결 유지 rank[px] == rank[py] 한 루트를 다른 루트 아래에 연결 1 증가 px == py 이미 같은 집합이므로 변경하지 않음 유지 경로 압축과 Rank를 함께 사용할 때 경로 압축이 없으면 Union by Rank로 구성된 트리에서 루트의 Rank는 트리 높이를 나타낸다. 경로 압축을 함께 사용하면 실제 높이는 낮아질 수 있지만 Rank를 다시 계산하거나 감소시키지 않는다. 이때 Rank는 현재 높이의 상한으로 사용하는 값 이며 실제 높이와 항상 같지는 않다. Union에서는 두 루트의 Rank만 비교 한다. 루트가 아닌 노드의 Rank를 집합 전체의 높이로 사용하지 않는다. 경로 압축과 Rank를 적용한 구현 다음 코드는 1부터 N까지의 원소를 초기화하고 두 최적화를 함께 사용한다. Rank가 같으면 첫 번째 루트를 대표자로 유지한다. N = 6 p = [0] * (N + 1) rank = [0] * (N + 1) def make_set(x): p[x] = x rank[x] = 0 def find_set(x): if x != p[x]: p[x] = find_set(p[x]) return p[x] def union(x, y): px = find_set(x) py = find_set(y) if px == py: return if rank[px] > rank[py]: p[py] = px elif rank[px] < rank[py]: p[px] = py else: p[py] = px rank[px] += 1 for x in range(1, N + 1): make_set(x) union(1, 3) union(2, 3) union(5, 6) print("부모:", p[1:]) print("Rank:", rank[1:]) print("6의 대표자:", find_set(6)) print("2와 3은 같은 집합:", find_set(2) == find_set(3)) print("1과 6은 같은 집합:", find_set(1) == find_set(6)) 출력: 부모: [1, 1, 1, 4, 5, 5] Rank: [1, 0, 0, 0, 1, 0] 6의 대표자: 5 2와 3은 같은 집합: True 1과 6은 같은 집합: False 대표자는 Union의 연결 규칙에 따라 달라질 수 있다. Rank를 기준으로 합치면 대표자가 항상 가장 작은 번호라는 보장은 없다. 연산 비용 비교 N은 원소 수이다. 구현 Find-Set Union 대표자 링크를 갖는 연결 리스트 O(1) 붙이는 리스트의 원소 수만큼 대표자 갱신 최적화 없는 부모 트리 최악 O(N) 루트 탐색을 포함해 최악 O(N) Rank를 이용한 트리, 경로 압축 없음 O(log N) O(log N) Rank와 경로 압축을 함께 적용 연산당 분할 상환 O(α(N)) 연산당 분할 상환 O(α(N)) α(N) 은 역 아커만 함수이며 매우 느리게 증가한다. 두 최적화를 함께 사용하면 연속된 연산들의 평균 비용이 매우 작아진다. 모든 개별 연산의 최악 시간이 O(1)이라는 뜻은 아니다. Make-Set 한 번은 O(1), N개 원소 전체 초기화는 O(N)이다. 부모 배열과 Rank 배열을 저장하는 공간은 O(N)이다.