728x90

그래프(graph)자료구조의 개념부터 해서 이와 관련된 disjoint-set 등의 다양한 알고리즘까지 쭉 정리해보려 한다.

하나의 게시글에 정리하려고 하니 양이 너무 많을 듯해서, 시리즈로 쪼개서 정리해보려 한다.

1. 그래프의 개념과 특징
2. disjoint set
3. Union Find 최적화(현재글)

Union Find 최적화

disjoint set을 구현하기 위한 연산으로는 Union function과 Find function 두 가지가 존재한다.

이 두 연산은 보통 트리에 대응하여 구현하는데, 이 때 트리가 균형잡혀있지 않고 한 쪽으로 쏠려있게 된다면 최악의 경우 시간복잡도가 O(N)이 된다. quik find연산을 사용할 때는 항상 O(N)의 시간복잡도가 사용된다. 이를 개선하기 위해서 두 가지 방법이 존재한다.

1. Union by Rank 2. Path Compression

 

위의 두 최적화 방법을 적용하면, 연산당 평균 시간 복잡도는 O(a(N))까지 줄어든다. 이때 a함수는 아주 느리게 증가하므로 사실상  O(1)이나 다름없다.  

 

Union By Rank

각 집합의 rank 즉 점수같은 것을 매기는 방식이다. 더 큰 집합일수록 더 큰 rank를 가지게 되고, union 연산에서 언제나 더 작은 집합을 더 큰 집합에 합치게 한다. 이로써 트리가 균형잡혀있게 강제하게 된다. 

앞에서 바로 rank를 점수같은 것이라고 했는데, 실질적으로 '이 집합을 나타내는 트리의 높이'를 rank라는 변수에 저장한다. 

 

이와 비슷하게 size 변수를 활용해서, 같은 방법으로 최적화하는 Union by size 기법도 있다. 

이름과 변수가 다를 뿐이지 실질적으로 최적화 하는 방법은 동일하므로 별도로 정리하지 않아도 될 거 같다.

(size는 트리안에 속한 변수의 갯수이고, rank는 트리의 높이라고 보면된다.)

 

기본적으로 smaller-to-larger trick'이라는 이름으로 트리 알고리즘의 최적화에 쓰이는 방식을 활용한 것이다. 

즉 이러한 최적화 방법을 사용하지 않았던 경우에는 최악의 경우 모든 노드들을 하나씩 탐색하며 root 노드를 찾은 다음 합해야했는데, 

지금의 경우, 각 트리의 rank 혹은 size만 알면 바로 합칠 수 있기 때문에 union하는 과정에서 최적화가 가능해지는 것이다. 

위의 그림을 보면 union by rank가 더 잘 이해될 것이다.

가장 왼쪽에 두개의 트리가 있고, node 1과 node 6을 연결해주고 싶다. 

이 때 각 노드의 root는 0과 5이다. 이를 기준으로 두 트리를 합쳐준다고 햇을때는 두번째의 경우와 가장 오른쪽의 경우인 두가지가 나온다. 

Uinon by rank를 통해 합친 가장 오른쪽의 경우가, 가장 최적화된 장법으로 합쳐진다. 

 

 

root 노드 x가 속한 트리가 바뀌면, 즉 다른 트리에 합쳐지게 된다면, x의 rank는 언제나 1이상 증가하고, (size 최적화의 경우) size는 언제나 두 배 이상 증가한다. 

  • rank가 더 크거나 같은 y에 합쳐지게 된다면, rank y는 rank x의 이상이므로, 합친 이후 x의 rank는 기존의 x의 rank에서 1이 더 커진다. y의 rank가 x의 rank보다 작은 경우엔, x의 rank는 변하지 않는다

이에 따라 x가 속한 트리가 바뀔때마다 x의 깊이는 1씩 증가한다. 

 

기본적으로 해당 방법은 union function을 기반으로 최적화하는 것이다. 

 

# UnionFind class
class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        # self.root = [0,1,2,3,4,5,6,7,8,9]
        self.rank = [1] * size
        # self.rank = [1,1,1,1,1,1,1,1,1,1]

    def find(self, x):
        while x != self.root[x]:
            x = self.root[x]
        return x
		
    def union(self, x, y):
        rootX = self.find(x)
        # x=1, rooX=1, self.rank[1]=1
        # x=2, rootX=1, self.rank[1]=2
        rootY = self.find(y)
        # y=2, rootY=2, self.rank[2]=1
        # y=5, rootY=5, self.rank[5]=1
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
                #self.root[5] = 1
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                #self.root[2] = 1 <- 합쳐주고
                #self.root = [0,1,1,3,4,5,6,7,8,9]
                self.rank[rootX] += 1
                #self.rank[1] = 2 <- root인 x의 rank가 1 늘어났다.
                #self.rank=[1,2,1,1,1,1,1,1,1,1]

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


# Test Case
uf = UnionFind(10)
# 1-2-5-6-7 3-8-9 4
uf.union(1, 2)
uf.union(2, 5)
uf.union(5, 6)
uf.union(6, 7)
uf.union(3, 8)
uf.union(8, 9)
print(uf.connected(1, 5))  # true
print(uf.connected(5, 7))  # true
print(uf.connected(4, 9))  # false
# 1-2-5-6-7 3-8-9-4
uf.union(9, 4)
print(uf.connected(4, 9))  # true

 

  • init : size가 N인 배열 두개를 만들어야 한다.
  • 트리의 균형이 보장된다.

증명. 모든 정점의 size가 N 이하인 것은 정점의 개수가 N개이므로 자명하다. 그리고,

  • size가 1일 때, rank는 1.
  • size가 3 이하일 때, rank는 2 이하.
  • size가 7 이하일 때, rank는 3 이하.
  • size가 15 이하일 때, rank는 4 이하.
  • …

임이 귀납적으로 증명 가능하다. 따라서, 모든 정점의 rank는 ⌈log2⁡N⌉ 이하이다.

위 두 보조정리로 인해, union by rank와 union by size의 시간 복잡도가 동시에 증명된다.

Union by size를 사용한다고 하자. 어떤 정점 x에 대해, x가 속한 트리가 바뀔 때마다 size가 2배 이상 증가한다.

그런데, size가 N 초과가 되는 것은 불가능하므로, x가 속한 트리가 바뀌는 횟수는 많아야 ⌈log2⁡N⌉ 번이다.

그런데, 정점 x가 속한 트리가 바뀔 때마다 정점 x의 깊이는 1씩 증가한다.

초기에 모든 정점들은 자신이 속한 트리의 루트였으므로 깊이가 0이었다.

따라서 연산들을 수행한 이후에도 각 정점의 깊이는 ⌈log2⁡N⌉ 이하이다. 따라서 find 함수는 언제나 ⌈log2⁡N⌉ 개 이하의 정점을 순회하게 되고, O(log⁡N) 시간에 작동한다.

 

 

Path Compression(경로압축)

find함수를 실행할 때, 최적화를 해주는 것이다. find함수 과정에서 경로 상의 모든 노드들을 곧바로 루트 노드아래에 달아주는 최적화 방법이다. 해당 최적화를 하지 않았을 경우에는 root노드를 찾기 위해서 순차적으로 부모노드를 거쳐야했다. 

이는 한번 root 노드를 찾고난 이후에도 같은 노드에 대해서 루트노드를 찾기 위해서 부모노드를 거쳐야 했던 것이다.

 

이에 대한 최적화를 하기 위해서, 한번 루트노드를 찾고난 이후에, 이미 탐색한 모든 요소들의 부모 노드들을 아예 루트노드로 업데이트해두면 된다. 이를 위해서 "재귀"를 활용한다.

 

최적화를 하기 전에는 위의 그림과 같으며, 각 노드들의 루트노드를 찾기 위해서는 주어진 경로를 일일이 다 따라가야했다. 

이를 아래의 그림과 같이 루트노드 아래에 바로 노드를 붙여서 find 루트 노드를 최적화 하는 것이다. 

 

# UnionFind class
class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        # self.root = [0,1,2,3,4,5,6,7,8,9]

    def find(self, x):
    # x=2, self.root[2]=1
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
		
    def union(self, x, y):
        rootX = self.find(x)
        #x=1, rootX=1
        #x=2, rootX=
        rootY = self.find(y)
        #y=2, rootY=2
        if rootX != rootY:
            self.root[rootY] = rootX
            # self.root[2] = 1
            # self.root = [0,1,1,3,4,5,6,7,8,9]<- 첫 union일때는 크게 다를게 없다.

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


# Test Case
uf = UnionFind(10)
# 1-2-5-6-7 3-8-9 4
uf.union(1, 2)
uf.union(2, 5)
uf.union(5, 6)
uf.union(6, 7)
uf.union(3, 8)
uf.union(8, 9)
print(uf.connected(1, 5))  # true
print(uf.connected(5, 7))  # true
print(uf.connected(4, 9))  # false
# 1-2-5-6-7 3-8-9-4
uf.union(9, 4)
print(uf.connected(4, 9))  # true

  • 시작하기 전에, root노드가 있는 배열을 생성하고 채우기 위해 O(N)의 시간복잡도가 소요된다. 
  • 최고의 경우, 부모노드 자체가 루트 노드인 경우  find함수의 시간복잡도는 O(1)이지만, 최악의 경우, O(N)이다. 그러나 평균적으로 시간복잡도는 O(logN)이다.

 

Union by Rank + Path Compression

# UnionFind class
class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        # Use a rank array to record the height of each vertex, i.e., the "rank" of each vertex.
        # The initial "rank" of each vertex is 1, because each of them is
        # a standalone vertex with no connection to other vertices.
        self.rank = [1] * size

    # The find function here is the same as that in the disjoint set with 
    # path compression.
    def find(self, x):
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    # The union function with union by rank
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

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


# Test Case
uf = UnionFind(10)
# 1-2-5-6-7 3-8-9 4
uf.union(1, 2)
uf.union(2, 5)
uf.union(5, 6)
uf.union(6, 7)
uf.union(3, 8)
uf.union(8, 9)
print(uf.connected(1, 5))  # true
print(uf.connected(5, 7))  # true
print(uf.connected(4, 9))  # false
# 1-2-5-6-7 3-8-9-4
uf.union(9, 4)
print(uf.connected(4, 9))  # true

  • N은 그래프 자료구조 내의 노드의 갯수이다. a는 Ackermann 함수를 의미한다. 일반적으로  O(a(N))은 O(1)과 가깝다.

α(N) (Ackermann 역함수)는 매우 빠르게 증가하는 함수인 애커만 함수로부터 정의된다.

거의 모든 정수 값에 대해, ≤4 이다. Ackermann 역함수는 계산 복잡도에서 흔히 쓰이는 함수들 가운데에 가장 느리게 증가하는 함수이다.

조금 더 빠르게 증가하는 함수 log⋆ 를 살펴보자.  은, 연산을 반복해서 이 되도록 하는 연산 횟수로 정의된다.

거의 모든 정수 값에 대해 log⋆이 α보다 조금 더 빠르게 증가하기는 하지만, 실제 구현 상에서 상수와 다를 바 없다는 것은 동일하다.

 

증명. 경로 압축이 있든 없든, 트리의 루트, 정점의 랭크, 그리고 트리 안에 있는 정점들은 그대로이다. 루트였던 정점 x가 다른 정점의 자식으로 합쳐질 때에도, rank[x]는 원래의 값을 유지한다고 가정하자.

이 때, 두 개의 트리가 합쳐지는 방법은 트리 A의 루트가, 트리 B의 루트 바로 아래에 붙는 방법밖에 없음에 주목하자. 정점 x가 루트 정점이 아니게 되는 순간, rank[x]는 더 이상 변할 일이 없음 또한 분명하다.

 

 

Reference

https://www.secmem.org/blog/2021/04/19/Union-Find-Time-Complexity-Proof/

https://www.youtube.com/watch?v=VHRhJWacxis 

 

728x90
저작자표시 비영리 변경금지

'CS STUDY > Algorithm&Data structure' 카테고리의 다른 글

[자료구조] Graph_2. Disjoint Set  (0) 2022.05.14
[자료구조] Graph_1. 그래프의 개념과 특징  (0) 2022.05.08
주요 DataStructure 정리_링크만첨부  (0) 2021.02.11
시간복잡도 & 공간복잡도  (0) 2021.02.11
재귀함수와 반복문의 차이  (0) 2021.02.11

+ Recent posts

티스토리툴바