프로그래밍 공부노트

quick-union의 경우 최악의 경우 N회의 배열 접근이 필요했는데 이를 개선하는 방법에 대해 알아보자.

개선 1. Weighted quick-union: 간단한 해결책은 tree와 tree를 연결할 때, 키가 큰 tree가 생기는 것을 피하는 것이다. 각 tree의 크기(오브젝트의 갯수)를 측정해서, 언제나 더 작은 tree가 더 큰 tree의 아래로 가게 만든다면 전체 tree가 세로로 길어지는 것을 막을 수 있다.

위의 경우 1이 속한 tree에는 오브젝트가 3개 있고, 6이 속한 tree에는 오브젝트가 6개 있으므로, 우측에 위치한 tree의 크기가 더 크다. weighted quick union 모델에서 0과 5를 연결시키면, 언제나 5가 0의 부모 오브젝트가 되도록 연결시키게 된다.

quick union에서는 아래처럼 더 작은 tree의 root(0)가 더 큰 tree의 root(5)의 부모 오브젝트가 되어 tree가 세로로 길어지는 상황이 발생하지만, 개선된 weighted quick union에서는 아래와 같은 연결이 발생하지 않는다.

quick-union에서 사용한 자료구조는 배열 1개였지만, weighted quick union에서는 tree의 크기를 저장하는 배열 size[N]이 하나 더 필요하다. size[i]는 i가 root인 tree에 속한 오브젝트의 갯수를 나타낸다.

quick union의 단점은 tree가 세로로 길다랗게 생긴 경우, 즉 오브젝트 x의 깊이가 N(오브젝트 전체 갯수)이 되는 경우이다. 하지만 이 개선된 모델에서는 어떤 오브젝트라도 깊이의 최대값이 lg N(lg N의 base는 2이다)밖에 되지 않는다.

어째서 오브젝트의 깊이는 최대 lg N일까?

x의 깊이가 1 증가한다는 것은 x가 속한 tree가 다른 tree에 병합된다는 것을 의미한다. 이 때 x가 속한 tree T1의 크기는 다른 tree T2의 크기보다 더 작거나 같아야 한다. 따라서 x의 깊이가 1 증가할 때, x가 속한 tree의 크기는 최소 2배 증가한다.

x가 속한 T1의 크기: 3, T2의 크기: 8

두 tree를 병합하면, T1의 크기가 더 작기 때문에 T1의 root가 T2의 root의 자녀 오브젝트가 된다.

병합 후 x의 깊이는 1이 증가했다. 새로운 T3의 크기: 11

x의 깊이가 증가하는 것은 x의 tree가 다른 tree의 child 오브젝트가 되어 병합되는 것과 같다. x가 속한 tree는 그럼 몇 번 병합될 수 있을까? x가 속한 tree가 2배만큼만 증가한다고 해도 최대 병합 횟수, 즉 x의 깊이의 최대값은 lg N이다.

weighted quick-union에서 find/connected query와 union command 수행 방법과 비용을 정리하면 아래와 같다.

먼저 find의 경우, quick-union에서와 동일한 방법으로 오브젝트의 root를 찾으면 된다.

이 때 걸리는 시간은 오브젝트의 깊이(depth, 오브젝트가 root로부터 몇 단계나 떨어져 있는지)에 비례한다. 앞서 살펴보았듯이 오브젝트의 깊이는 아무리 커도 lg N을 넘지 않는다.

connected의 경우 두 오브젝트에 대해 find를 수행해 각각의 root를 비교한다. 따라서 두 오브젝트의 깊이의 합에 비례하는 시간이 소요된다.

union의 경우, quick-union에서는 union(p, q)는 언제나 p의 root를 q의 root로 변경했다. 그러나 weighted quick-union에서는 p가 속한 tree의 크기와 q가 속한 tree의 크기를 비교해서, 더 작은 tree의 root가 더 큰 tree의 root의 자녀 오브젝트가 되도록 배치한다.

union 실행에 걸리는 시간은 두 오브젝트의 root가 주어진 경우 constant이다.

weighted quick union에서 초기화/union/find에 드는 비용을 비교해 보면 다음과 같다.

임의의 오브젝트의 깊이가 최대 lg N이라는 것 덕분에 weighted quick union은 속도 면에서 월등하게 개선되었다. lg N은 N에 비해 증가 속도가 매우 느리다. 예를 들어 N이 10억일 때, lg N의 값은 약 30에 불과하다. 이렇게 간단한 개선으로 10억회 연산할 것을 30번의 연산만으로 해결할 수 있게 되었지만, 간단한 방법으로 더욱더 효율적인 알고리즘을 디자인할 수 있다.

개선 2. path compression

두번째 개선은, 만약 오브젝트 p의 루트를 구하게 될 일이 생기면(=root(p) 메소드를 호출하게 된다면) 루트를 구한 뒤 p를 그 루트에 직접 연결하는 것이다. 이 작업을 통해 tree가 매우 평탄해지는 효과가 생긴다.

이런 모양의 tree가 있을 때, 0의 root를 구한다면, 0을 직접 그 root인 5에 연결시킨다.

또 8의 root를 구하게 된다면 역시 8을 root인 5에 직접 연결시킨다.

tree가 더 납작해지는 것을 확인할 수 있다.

이 path compression을 구현하기 위해서는 find() 메소드에 하나의 루프를 추가해야 하지만, 약간 변형된 형태로는 한줄만 추가해서 구현할 수 있다. 이 방법은 이론적으로 tree를 완전히 평탄화 시키지는 못하지만 실제 상황에서는 거의 그만큼 좋다. quick union에서 사용했던 find 메소드에서 단 한줄의 코드만 추가하면 된다. 모든 노드는 아니고 하나 걸러 하나씩 오브젝트들이 자신의 grandparent 오브젝트를 가리키게 된다(따라서 전체 길이가 절반으로 짧아진다).

1
2
3
4
5
6
7
8
9
10
    private int find(int i)
    {
        while (i != id[i]) 
        {
            id[i] = id[id[i]]; // 추가된 코드 단 한줄
            i = id[i];            
        }
        
        return i;
    }
Colored by Color Scripter
cs

증명은 생략되었지만, weighted quick-union에 path compression를 더했을 때 연산 횟수는 비약적으로 적어진다. 비어있는 자료구조에서 시작해서 N개의 오브젝트에 대해 M개의 union-find(아무렇게나 뒤섞인) 작업을 수행했을 때 드는 배열 접근 횟수는

c(N + M lg* N)회보다 작거나 같다.

lg *N은 iterated logarithm이라고 불린다. log 함수를 반복해서 적용했을 때의 값으로, 증가 속도는 매우 매우 느리다.

(출처: https://en.wikipedia.org/wiki/Iterated_logarithm)

이론적으로 WQUPC(weighted quick union with path compression)은 선형은 아니다. 그리고 union-find에 대한 선형-시간 알고리즘이 없다는 것이 증명되어 있다. 하지만 log* N의 증가 속도가 극히 느리기 때문에, 현실에서 사용할 때는 선형이라고 표현해도 무리가 없을 정도이다.

지금까지 알아본 dynamic connectivity에 대한 union-find 알고리즘의 연산 횟수를 정리해 보면 다음 표와 같다.

10^9개의 오브젝트에 대해 10^9회의 union-find operation을 수행했을 때, 최악의 알고리즘을 사용하면 무려 30년이 걸릴 것을 효율적인 WQUPC 알고리즘을 사용하면 단 6초만에 해결할 수 있다.

지금까지 dynamic connectivity에서의 union-find 알고리즘에 대해 알아보았다. 여기서 얻을 수 있는 교훈은, 이런 종류의 문제를 해결할 때 좋은 알고리즘이 문제를 해결해 주지, 컴퓨터의 성능이 좋아진다고 해서 도움이 되지 못한다는 것이다.

1-3 더 나은 방법: Quick-Union [Lazy Approach]

2017. 2. 19. 22:22

[엮인 글 링크]

Colored by Color Scripter

앞서 살펴본 quick find가 너무 느렸기 때문에, 더 나은 대안이 필요하다.

다음으로 살펴볼 알고리즘은 quick union이다. quick find가 eager approach였던 대 비해, 이 방법은 lazy approach이다. lazy라는 이름이 붙은 이유는, 꼭 해야할 상황이 아니면 연산 수행을 피하기 때문이다.

quick union에서도 자료구조로 배열을 사용한다. 이 점은 quick find와 같다. 하지만 배열의 해석 방법은 다르다.

이 배열은 tree의 집합을 나타낸다. 배열의 원소들은 각 오브젝트의 parent 오브젝트, 자신보다 더 위에서 자신과 연결되어 있는 오브젝트를 나타낸다. 예를 들어 8의 parent는 6이고, 6의 parent는 5이다.

x = i일 때부터 반복적으로 id[x]의 값, 즉 부모 오브젝트를 구했을 때 부모가 자기 자신인 오브젝트가 i의 root이다.

예를 들어 오브젝트 8의 경우, id[8] = 6, id[6] = 5, id[5] = 5(부모가 자기 자신)이므로, 8의 root는 5이다.

이 자료구조에서 find/connected query와 union command를 수행해 보자.

1. find/connected query

quick union에서 같은 root를 갖는 오브젝트들은 서로 같은 connected component에 속해 있다. 위 그림을 예로 들면, 같은 connected component에 속한 오브젝트 0, 1, 2는 모두 root가 0이다. 그러므로 find query는 곧 root의 값을 구하는 것과 같다. root를 찾기 위해서는 오브젝트의 parent가 자기 자신일 때까지 parent를 찾아가면 된다. 이 메소드는 root에 도달할 때까지 계속 자신의 부모 오브젝트를 추적한다. 이 메소드를 실행하는 데에는 i 오브젝트의 깊이(depth)이만큼 배열 접근이 필요하다. '깊이'는 오브젝트가 뿌리로부터 몇 단계나 떨어져 있는지를 나타낸다.

    private int find(int i)
    {
        while (i != id[i]) i = id[i];
        return i;
    }

connected query를 알아보자. p와 q의 root가 동일하다면, 둘은 서로 연결되어 있다.

ex) 2의 root는 0, 4의 root는 3이므로, 둘은 서로 연결되어 있지 않다.

8의 root는 5, 5의 root는 5로 서로 같은 root를 가지고 있다. 둘은 서로 연결되어 있다.

    public boolean connected(int p, int q)
    {
        return find(p) == find(q);
    }

Colored by Color Scripter

2. union command

p와 q가 속한 두 개의 connected component를 병합하려면, p의 root의 id를 q의 root의 값으로 수정한다.

위 그림에서 4와 7을 연결시킨다면, 4의 root가 3이고, 7의 root가 5이므로, id[3]의 값을 5로 바꾼다.

quick find에서 너무 많은 원소의 값이 변경되었던 것과 달리, quick union에서는 단 한 원소의 값만 바뀐다.

1
2
3
4
5
6
    public void union(int p, int q)
    {
        int i = find(p);
        int j = find(q);
        id[i] = j;
    }

find query와 union command에 드는 비용을 알아보자.

먼저 find query는 해당 오브젝트의 깊이만큼의 비용이 발생한다.

union command는 find query를 오브젝트 p와 q에 대해 각각 수행하므로 p와 q의 깊이를 합한 것 만큼의 비용이 발생한다.

이 코드는 quick-find에 비교했을 때 for문이 없고(대신 root 메소드에 while문이 있다) 더 간결하다. 하지만, 최악의 경우(tree가 세로로 긴 경우)에는 find의 비용이 너무 크다. 최대 N회의 배열 접근이 필요할 수 있기 때문에, N의 값이 커질 때 사용하기에는 부적절하다.

최악의 경우 tree가 이렇게 생겼다면 오브젝트 5에 대해 find query 수행시 parent를 찾는 명령을 6번 수행해야 5의 root를 찾을 수 있다.

quick-union에서 초기화/find/union에 드는 비용을 정리하면 다음과 같다.

1-2 첫번째 방법: Quick-Find [Eager Approach]

2017. 2. 18. 15:52

[엮인 글 링크]

dynamic connectivity problem을 풀기 위한 첫 번째 알고리즘, quick-find에 대해 알아보자. 이 방법은 eager algorithm이라고로도 불린다.

quick-find 알고리즘 구현을 위해 필요한 자료구조는 길이가 N인 일차원 배열이다. 배열의 이름을 id라고 하자.

오브젝트 p와 q는, id[p]와 id[q]의 값이 같다면, 그리고 같을 때만(if and only if) 서로 연결되어 있다.

배열 해석:

0, 1, 2가 서로 연결되어 있다.

3, 4, 8, 9가 서로 연결되어 있다.

5, 6이 서로 연결되어 있다.

7이 서로 연결되어 있다.

이제 이 자료구조에 대해 find/connected query, union command를 수행해 보자.

먼저 find의 경우, p가 어떤 connected component에 속해 있는지 알아보려면, 단지 id[p]의 값을 구하면 된다.

connected의 경우, p와 q는 서로 연결되어 있는가에 대한 답은 배열의 id[p]와 id[q]의 값이 같은지 확인해 보면 된다.

connected(1, 6) = ?

id[1] = 0; id[6] = 5로 각각의 값이 다르므로, 1과 6은 서로 연결되어 있지 않다.

union의 경우, p와 q가 속한 connected component를 합병하기 위해서는, 값이 id[p]인 모든 원소의 값을 id[q]로 바꿔야 한다.

union(1, 6) 명령을 실행하면,

id[6] = 5이고 id[1] = 0이므로 id[ ] = 0인 모든 원소의 값을 5로 변경한다.

이 방법의 문제점은 너무 많은 원소의 값을 바꿔야 하는 상황이 있다는 점이다.

이 모델에서 connected query와 union command, 그리고 초기화를 수행하기 위해 배열의 원소에 몇 번 접근해야 할까?

먼저 초기화 시에는 각각의 오브젝트에 접근해 id를 오브젝트 이름으로 설정하므로 N회의 array access가 발생한다.

1
2
3
4
5
6
    public QuickFindUF(int N)
    {
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
cs

connected query시에는, 각각의 배열 원소에 접근(find)해서 값을 비교하기만 하면 되기 때문에 단 2회의 array access가 발생한다.

connected(p, q) 자바 코드

1
2
    public boolean connected(int p, int q)
    { return id[p] == id[q]; }
cs

반면 union command 수행시는 먼저 id[p]와 id[q]에 접근해 값을 저장하고, 배열의 모든 원소에 접근해서 그 값을 id[p]와 비교하고, 만약 같다면 id[q]의 값으로 바꿔야 한다.

union(p, q) 자바 코드

1
2
3
4
5
6
7
    public void union(int p, int q)
    {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++)
            if (id[i] == pid) id[i] = qid;
    }
Colored by Color Scripter
cs

이 경우에는 처음에 id[p]와 id[q]의 값을 새 변수에 저장하기 위해 배열의 원소에 두 번 접근하고, for 문을 통해 배열 id의 모든 원소에 한번씩(원소의 값이 pid와 같은 경우, 두번씩) 접근하기 때문에 최대 2N + 2회만큼 배열의 원소에 접근하게 된다.

만약 N개의 오브젝트에 대해 N회의 union command를 수행한다면, N^2회(quadratic algorithm)만큼의 배열 접근이 이뤄져야 하는데 이 비용은 지나치게 비싸다. N의 값이 커질수록 연산 횟수가 제곱만큼 증가하기 때문에, N의 값이 클 경우 너무 느리다.

quick-find 알고리즘에서 초기화/union/find를 위한 배열 접근의 횟수는 다음과 같다.

1-1 Dynamic Connectivity 문제

2017. 2. 17. 22:51

Coursera https://www.coursera.org/learn/algorithms-part1 강의 정리

[엮인 글 링크]