위 그림에서 u와 v가 서로 연결되 있는지 어떻게 확인할 수 있을까요?
눈으로 확인하는 것은 굉장한 노력이 필요하지만, 컴퓨터는 같은 집합에 있는지 여부만 확인함으로써 간단하게 알아낼 수 있습니다.
이와 비슷하게 각 웹페이지가 서로 연결되어 있는지, 네트워크가 서로 연결되어 있는지 확인하는 것도 같은 맥락으로 볼 수 있습니다.
이번 포스팅에서는 이전 탐욕 알고리즘 포스팅을 응용하여 u와 v가 연결되어 있는지를 살펴보는 방법에 대해서 알아보도록 하겠습니다.
목차
0. 배경
해결해야 할 내용을 최소한으로 줄여서 문제를 파악해보도록 하겠습니다.
위 사진은 tree 형태로 component를 나타낸 것입니다. (linked list, array로도 표현할 수 있습니다!)
우리가 파악하고 해결 해야 할 문제는 아래와 같습니다.
1번 노드가 어느 component에 있는지 확인 -> find(1)
1번 노드와 3번 노드가 연결되어 있는지 확인 -> find(1) == find(3)
1번 노드와 3번 노드가 속해 있는 component를 하나로 묶기 -> union(1,3)
또한 위 문제는 집합 간에 교집합이 없어야 합니다. 이를 disjoint set이라 부릅니다.
위 미로를 예로 들면 한 벽이 연결되어있지 않은 다른쪽 벽과 같은 component에 있다는 것은 모순됩니다. (당연한 이야기!!)
그래프를 만들기 위해서 필요한 연산은 아래와 같이 총 3가지입니다.
첫 번째는 make_set(v)로, v라는 요소를 가진 set을 만드는 연산
두 번째는 find(v)로 v를 가진 set의 이름을 반환하는 연산
세 번째는 union(u,v)로 원소 u와 원소 v를 갖고 있는 set을 합치는 연산
세 연산을 통해 문제를 해결할 수 있다면, 이제 우리가 파악해야 할 것은 효율적인 처리가 가능한 자료구조와 알고리즘입니다.
1. linked list 이용
각 원소는 set의 맨 처음으로 가는 포인터와 다음 요소로 가는 포인터를 가집니다.
각 set의 이름은 맨 앞이 됩니다. boat의 경우 b가 이름이 되고, we의 경우 w가 이름이 됩니다.
시간복잡도를 살펴보면
make_set(v)는 바로 만들 수 있기 때문에 O(1)이고,
이름을 찾는 find(v)의 경우에도 바로 set의 맨 첫 위치(이름)로 갈 수 있으므로 O(1)이 됩니다. 다만 어떤 원소가 집합에 있는지 여부를 찾는다면 집합의 맨 앞부터 순서대로 지나가면서 찾아야하는 불편함이 생깁니다.
union(u,v)의 경우 u가 속해있는 리스트의 set의 맨 처음(이름)으로 가는 포인터를 v가 속해있는 set의 맨 처음(이름)으로 바꿔줍니다. u->v가 되는 것이죠. (반대도 가능하긴 합니다!)
만약 3개의 set을 생성하고 서로 이어준다고 생각하면 아래와 같은 과정으로 만들 수 있습니다.
make_set()으로 만들고, union()을 합니다.
이 과정이 n개의 데이터에서 m번의 union이 발생한다면 O(m^2)시간이 걸리게 됩니다.
여기서 더 효과적으로 union을 만들어주는 방법을 생각해볼 수 있습니다.
이전 union은 방향을 하나 정해서 합해줬다면, 이제는 두 연결리스트의 길이를 비교해서 더 짧은 쪽의 데이터를 긴 쪽에다가 붙이면 더 효율적으로 동작하게 됩니다. 이것을 weighting-union heuristic(가중치 유니온 휴리스틱)이라고 부릅니다.
weighting-union heuristic을 사용하면 A와 B가 합쳐져서 새로운 B가 되었을 때 새로운 B는 A의 길이의 2배 이상입니다. (새로운 B가 되었다는 말은 최소한 B의 길이가 A의 길이 이상이라는 이야기!!)
길이가 짧은 쪽이 길이가 긴 쪽으로 합쳐졌다는 이야기이므로 최소한 길이가 같아야지만 계속해서 포인터가 변경될 수 있는 환경이 만들어 지는 것입니다.
이 말은 어떠한 원소도 log_2(n)번보다 더 많이 이동할 수 없습니다. (앞으로 밑이 2인 로그를 lg로 부르겠습니다)
한 원소에 대해 O(lg n)이므로 전체 원소에 대해서 O(n lg n)이 됩니다.
만약 union을 (1,2)부터 ... (1,8)까지 한다면 1의 소속은 단 1번만 바뀌게 됩니다.
왜냐면 두 번째부터 1이 들어간 쪽의 길이가 더 길어지기 때문이죠.
이제 한 원소의 포인터가 바뀌는 횟수가 왜 최대 O(lg n)인지 조금 이해가 가셨나요?!
2. array 이용
매우 직관적인 방법입니다. array 안에 id값을 넣으면 됩니다.
다만 이 방법의 아쉬운 점이라면 어느 set에 들어있는 원소의 개수를 구해야 하면 모든 원소를 다 확인해야 한다는 점입니다.
즉 linked list와 array는 어떤 작업을 많이 하냐에 따라 효율이 달라집니다.
find(x)의 경우 set_id[x]만 확인하면 됩니다. 따라서 O(1)입니다.
union(x,y)의 경우 set_id[y]를 갖고 있는 원소들의 set_id를 set_id[x]로 변경합니다.
array의 union에서도 weighting-union heuristic을 사용할 수 있고, 이 경우 linked list 방식의 union과 같은 시간이 소요됩니다. 한 원소에 대해 O(lg n)이 걸리게 됩니다. (list와 같은 원리입니다!!)
3. tree 이용
3.0. 단순한 방법
하나의 component는 하나의 트리로 표현합니다.
그리고 전체 그래프가 모든 집합을 표현합니다.
집합의 이름은 root원소이고, 각 원소는 부모로 향하는 포인터를 가집니다.
find(x)는 x에서 출발하여 parent로 향하는 포인터를 따라 root로 이동하여 root값을 반환합니다.
union(x,y)는 find(x)원소를 find(y)의 child node로 만듭니다.
만약 union(x1,x3)을 한다면 아래 그림과 같습니다.
x1, x2로 구성된 set의 root는 x2이고, x3으로 구성된 set의 root는 x3입니다.
이제 union(x1,x3)은 x1의 root인 x2를 x3의 child node로 만듭니다.
여기서 union(x1,x3)은 find(x1), find(x2), find(x3)을 포함하게 됩니다.
find(x1)은 포인터 이동이 1회 필요하고, find(x2)와 find(x3)은 포인터 이동이 필요하지 않습니다.
즉 union(x1,x3)은 한 번의 포인터 조작만으로 해결할 수 있습니다. (x2를 x3와 연결하는 부분은 카운트하지 않습니다. 포인터 이동이 아닌 포인터 할당이니까요!)
위와 같은 작업을 x_n까지 한다고 생각해봅시다.
union(x1,x3)은 find(x1)만 변하면 되기 때문에 포인터 이동횟수가 1이었는데, union(x1,x4)는 find(x1), find(x2) 값이 변해야 하기 때문에 포인터 이동횟수가 2가 됩니다.
이걸 x_n까지 계속하게 되면 포인터 이동 횟수는 n-2까지 늘어나게 됩니다.
즉 union(x1,x2) ... union(x1,x_n)은 포인터 이동횟수가 1+2+3+...+(n-2)가 되어서, 등차수열의 합을 계산하면 O(n^2)시간이 필요하다는 것을 알 수 있습니다. 이 말은 weighting-union heuristic을 사용한 list/array의 O(n lg n)보다 비효율적이라는 이야기가 됩니다.
3.1. 트리의 무게를 고려한 방법
만약 트리가 갖고 있는 weight가 더 작은, 혹은 rank가 더 낮은 트리를 weight가 더 크거나 rank가 더 높은 트리에 연결하면 어떻게 될까요?
반대의 경우에 비해서 더 낮은 rank를 갖게 됩니다.
이렇게 트리의 높이를 낮추면 find를 더 빠르게 수행할 수 있게 됩니다.
이 방법을 사용한다면 n개의 원소를 갖고 있을 때 forest(전체)에 있는 어떤 트리도 높이가 lg n을 넘을 수 없습니다.
즉 O(n) union-find operation은 최대 O(n lg n) 시간이 소요되는 것이죠.
만약 n개의 요소에 대해 m번의 union, find가 있다면, 아래 그림과 같이 union될 것입니다. 이 말은 m번의 union, find가 있다면 시간복잡도는 최대 O(m lg n)이 된다는 이야기겠죠.
아래 예시에 직접 대입해보면, 최대 3번(= lg 8) find(x)가 변경되는데, 이걸 m번 반복한다는 이야기가 됩니다.
O(m lg n), 이제 이해 되셨죠? 이전 방법에 비해 조금 더 효율적으로 변했습니다.
3.2 path compression 방법
경로압축 방법은, find(z)를 수행할 때 방문하는 노드들을 root의 child로 만드는 것입니다.
한번에 이해하기 힘들 수 있으니 아래 예를 살펴봅시다.
순서대로 union(1,2), union(3,4), union(1,6), union(1,4), union(7,8), union(5,8), union(3,8)을 순서대로 진행한 모습입니다.
가장 눈여겨봐야할 부분은 마지막 부분입니다. union(3,8)을 했을 때 8의 parent가 2가 됩니다. 그리고 union(3,8) 과정에서 find(3)이 수행되는데, 이 find(3)에 의해서 3은 root의 child node가 됩니다. 4 아래 있던 3이 root 바로 아래인 2 밑으로 내려왔죠?
path compression 방식과 weighting-union heuristic 방식을 모두 사용하는 경우 아래 표와 같은 결과값이 나오게 됩니다.
n과 F(n)로 구성된 표를 보면 원소의 개수가 한 원소의 포인터 이동에 미치는 결과를 나타냅니다.
만약 원소가 4개라면 한 원소의 포인터 이동은 최대 2번까지 가능하다는 이야기입니다.
이를 좀 더 보기 좋게 바꾼 표가 n과 G(n)으로 구성된 표입니다.
n의 범위 내에 위치하면 최대 G(n)만큼 포인터 이동이 필요하다는 이야기입니다.
(5의 위치가 어색해보이는 이유는 오타가 나서 제가 임의로 수정했습니다.. ㅋㅋㅋ)
즉, union-find operations의 시간복잡도가 O(nG(n))이 되는 것이죠.
O(n lg n)에 비해서 원소의 개수가 16이 넘어가면서부터 차이가 벌어지게 됩니다.
이전에 배웠던 Kruskal 알고리즘으로 돌아가보겠습니다.
각 에지들을 정렬하는데 O(m lg m)이 걸렸고 (2번째 줄)
n개의 disjoint set을 초기화하는데 O(n)이 걸렸습니다. (4번째 줄)
이제 while문을 살펴보면 루프를 최대 m번 수행하게 됩니다. (5번째 줄~)
disjoint set data를 사용하고, 1회 반복에서 find, equal, merge(union)같은 동작을 호출하는 횟수가 상수라면, m번 반복에 대한 시간복잡도는 weighting-union heuristic 방식을 사용하는 경우 O(m lg n) 이거나, path compression 방식까지 사용한다면 O(mG(m))이 될 것입니다.
이제 세 가지 케이스를 모두 비교해보면 m >= n-1이기 때문에 W(m,n)은 O(m lg m)만큼의 시간이 걸리게 됩니다.
이것으로 탐욕 알고리즘 (그리디 알고리즘)을 모두 살펴봤습니다.
이전 포스팅에서는 수를 직접 다루는 느낌이었다면 이번 포스팅에서는 자료구조끼리 크기, rank를 비교해서 탐욕 알고리즘을 사용한다는 점에서 약간의 차이가 있었습니다.
하지만 공통적으로 현 상황에서 최선의 수를 생각한다는 것은 동일한 맥락이었습니다. (오늘 내용에서는 매번 weight 혹은 rank가 더 낮은 쪽으로 가는 것이 더 탐욕적으로 작동하는 것이었습니다!)
아마 직관적으로 이해하기에 가장 좋은 알고리즘이 아닐까 생각합니다 ㅎㅎ
그렇다면 다음 포스팅에서는 맞지 않는 것은 지워버리는 식으로 전진하는 백트래킹에 대해서 알아보도록 하겠습니다 :)
읽어주셔서 감사합니다!!
최근댓글