[엮인 글 링크]
1-2 첫번째 방법: Quick-Find [Eager Approach]
1-3 더 나은 방법: Quick-Union [Lazy Approach]
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; } | cs |
이 경우에는 처음에 id[p]와 id[q]의 값을 새 변수에 저장하기 위해 배열의 원소에 두 번 접근하고, for 문을 통해 배열 id의 모든 원소에 한번씩(원소의 값이 pid와 같은 경우, 두번씩) 접근하기 때문에 최대 2N + 2회만큼 배열의 원소에 접근하게 된다.
만약 N개의 오브젝트에 대해 N회의 union command를 수행한다면, N^2회(quadratic algorithm)만큼의 배열 접근이 이뤄져야 하는데 이 비용은 지나치게 비싸다. N의 값이 커질수록 연산 횟수가 제곱만큼 증가하기 때문에, N의 값이 클 경우 너무 느리다.
quick-find 알고리즘에서 초기화/union/find를 위한 배열 접근의 횟수는 다음과 같다.
