Week 3 of Data structures - Disjoint sets
이번에는 3주차의 강의의 후반부의 내용인 Disjoint sets에 대해 배웠다.
우선 위와 같은 미로를 보여주며 A지점과 B지점이 서로 만날 수 있는지 질문을 던지며 시작한다.
이처럼 닿을 수 있는 것을 알 수 있고,
또 다른 길이 있는 것도 알 수 있다.
하지만 위와 같은 경우에는 불가능함을 확인할 수 있다.
위의 내용을 잠시 뒤로하고 Disjoint set의 동작들에 대해 알아보는데 MakeSet, Find, Union이 있으며,
Preprocess, IsReachable을 통해 추가적인 기능이 있음을 알았다. 이제 바로 예시로 넘어가면,
네트워크를 구성할 때 1~4까지의 기기를 MakeSet을 통해 추가하고,
Find API를 통해 1번 기기와 2번 기기가 서로 연결이 되었는지 알아보는데 아직 연결이 되지 않았으므로 당연히 False가 반환된다.
Union을 통해 3, 4번 기기를 연결하고
5번 기기를 추가한 뒤,
Union을 통해 3, 2번 기기를 연결한다.
이후 Find를 통해 1, 2번이 연결이 되었는지를 물어보고 여전히 False임을 알 수 있다.
이번엔 1, 4번을 Union으로 묶어주며,
1, 2번이 연결되어있으므로 True가 반환되는 것을 확인하였다.
예시로 n개의 대상을 정수로 나타내고,
이들 중 가장 작은 원소를 고유의 ID로 사용한다고 한다.
바로 간단한 예시로 들어와서 각 set의 최소값을 파란색으로 표시했으며, 이들이 각 set의 최소값이자 ID가 되는 셈이다.
MakeSet은 가장 작은 값을 가지고 있는 인덱스를 가지게 되고 Find는 가장 작은 원소를 반환하게 된다. 이들의 복잡도는 O(1)이다.
Union은 i번째의 ID와 j번째의 ID가 같을 시 그대로 병합하고 그렇지 않다면 작은 값을 찾아 그 원소를 기준으로 병합하게 된다.
이제까지 배열이나 리스트는 선형이기 때문에 처리시간이 선형적으로 증가했고 이에 대해 bottleneck현상이 발생했다. 이를 해결하기 위한 방안으로 Union이 등장했고 이를 Linked list로 연결하는데 약간은 다르게 연결하게 된다.
위와 같은 두개의 리스트가 있을 때(각각의 마지막 원소가 ID) 이 둘을 연결하게 되면,
기본적으로 위와 같은 형태이다. (마지막 원소인 8만 ID로 인식)
우선 장단점이 먼저 나오게 되고 바로 이전에 언급한 Union으로 넘어가자면,
같은 리스트를,
위와 같이 분기점을 가진 리스트로 연결하게 된다. 마치 이전 시간의 트리구조로 변형이 되는 것이다.
기존의 linked list의 병합은 끝원소를 찾아 연결하는 이유로 시간이 많이 소요됨에 반해 트리형태의 병합은 금방 이루어 질 수 있다.
각각의 셋은 root를 가진 트리구조를 표방하며 마지막원소는 각 트리의 ID이자 root가 된다.
배열을 통해 위의 구조를 다시 보자면 각 배열에 인덱스에 들어선 값들이 각 인덱스(노드)의 부모 노드가 누구인지를 알려주게 된다.
MakeSet과 Find의 순서와 Running time이고,
위와 같은 두개의 트리가 있을 때 이를 병합하는 방법은 두가지이다.
오른쪽 트리를 왼쪽트리로 병합시킬 수 있고 위와 같이 왼쪽트리를 오른쪽으로 병합할 수 있다.
이 때 병합할 시 트리의 높이가 낮은 편으로 병합을 하는 편이 유리하다. (이유는 복잡도가 낮아진다)
다시 한번 더 예시를 틀어주며 오른쪽 트리가 왼쪽트리보다 높이가 작으므로 오른쪽 병합 방식이 더 잘 되었다고 설명한다.
이번에는 Union 진행 시 Rank에 따라 하는 방법을 알아본다.
MakeSet 기능에 rank[i] <- 0 이라는 단계가 추가 되었다.
Union은 새롭게 rank를 비교하며 작동하도록 기능이 변경되었으며,
기본적인 성능은 크게 다르지 않음을 보여준다.
예시를 통해 다시 이해를 해보면 MakeSet으로 1~6까지의 원소를 추가하면,
각각이 자리를 잡게 되어 자기 자신이 부모가 되어 root가 된 것을 볼 수 있다.
이후 Union(2, 4)를 통해 2,4번 노드를 연결하는데,
이렇게 트리의 구성이 변경되고 2번 노드의 부모 노드가 4번으로 바뀐다. 이때 4번 노드의 rank도 1로 변경되었다.
또 다시 Union(5, 2)를 통해,
5번 노드도 4번 노드를 부모 노드로 삼고,
Union(3, 1)로 다시한번 변경이 되고,
Union(2, 3)을 통해,
1번 노드가 4번노드를 포함한 서브트리의 부모노드가 되었다. 동시에 rank도 2로 상승했다.
마지막으로 Union(2, 6)을 통해 6번 노드를 1번 노드 밑에 붙이게 된다.
어떤 노드 i에서든 rank[i]는 i의 트리의 높이와 동일하다 는 내용을 시사한다.
이번에는 Lemma라는 개념이 등장하며 어떤 트리의 높이든 최대 log2n이라고도 하며 또다른 내용으로는 k 높이를 가진 어떤 트리이든 최소 2^k만큼의 노드를 가진다고도 한다.
이에 대한 증명을 진행하며,
Union과 Find의 복잡도는 O(log n)이라며 정리한다.
마지막 개념으로 Path Compression에 대한 내용을 소개한다. 위의 트리에서 Find(6)를 통해 6번 노드부터 root까지 도달하는 길을 표시한 상태이다.
약간 다른 트리에서느 path가 더 짧은 것을 알 수 있는데 이를 path compression이라고 부른다.
이때 Find는 i가 root가 아니라면 해당 노드의 부모노드를 찾아 parent[i]로 다시금 업데이트 한다. 이런 과정을 통해 압축이 가능해지는 것 같다.
정의 상으로는 위와 같은 서술이 되며 바로 예시로 넘어가본다.
n개의 노드가 있을 때 이를 path compression한다면 이에 대해 각각은 log n의 계층으로 줄어드게 된다. 이 때 n의 최대값에 해당하는 것들에 log2를 취해보면 바로 위 계층의 최대값이 된다는 것을 간단히 알 수 있다.
다시 등장한 Lemma의 내용은 위와 같은 내용으로 바뀌었다.
해당 동작의 amortized time, 복잡도는 O(log n)이라고 한다. 실질적인 n값은 최대 5라고 한다. (2^65536값을 넘어가는 일은 거의 없으므로)
이번에는 3주차의 강의의 후반부의 내용인 Disjoint sets에 대해 배웠다.
우선 위와 같은 미로를 보여주며 A지점과 B지점이 서로 만날 수 있는지 질문을 던지며 시작한다.
이처럼 닿을 수 있는 것을 알 수 있고,
또 다른 길이 있는 것도 알 수 있다.
하지만 위와 같은 경우에는 불가능함을 확인할 수 있다.
위의 내용을 잠시 뒤로하고 Disjoint set의 동작들에 대해 알아보는데 MakeSet, Find, Union이 있으며,
Preprocess, IsReachable을 통해 추가적인 기능이 있음을 알았다. 이제 바로 예시로 넘어가면,
네트워크를 구성할 때 1~4까지의 기기를 MakeSet을 통해 추가하고,
Find API를 통해 1번 기기와 2번 기기가 서로 연결이 되었는지 알아보는데 아직 연결이 되지 않았으므로 당연히 False가 반환된다.
Union을 통해 3, 4번 기기를 연결하고
5번 기기를 추가한 뒤,
Union을 통해 3, 2번 기기를 연결한다.
이후 Find를 통해 1, 2번이 연결이 되었는지를 물어보고 여전히 False임을 알 수 있다.
1, 2번이 연결되어있으므로 True가 반환되는 것을 확인하였다.
예시로 n개의 대상을 정수로 나타내고,
이들 중 가장 작은 원소를 고유의 ID로 사용한다고 한다.
바로 간단한 예시로 들어와서 각 set의 최소값을 파란색으로 표시했으며, 이들이 각 set의 최소값이자 ID가 되는 셈이다.
MakeSet은 가장 작은 값을 가지고 있는 인덱스를 가지게 되고 Find는 가장 작은 원소를 반환하게 된다. 이들의 복잡도는 O(1)이다.
Union은 i번째의 ID와 j번째의 ID가 같을 시 그대로 병합하고 그렇지 않다면 작은 값을 찾아 그 원소를 기준으로 병합하게 된다.
이제까지 배열이나 리스트는 선형이기 때문에 처리시간이 선형적으로 증가했고 이에 대해 bottleneck현상이 발생했다. 이를 해결하기 위한 방안으로 Union이 등장했고 이를 Linked list로 연결하는데 약간은 다르게 연결하게 된다.
위와 같은 두개의 리스트가 있을 때(각각의 마지막 원소가 ID) 이 둘을 연결하게 되면,
기본적으로 위와 같은 형태이다. (마지막 원소인 8만 ID로 인식)
우선 장단점이 먼저 나오게 되고 바로 이전에 언급한 Union으로 넘어가자면,
같은 리스트를,
위와 같이 분기점을 가진 리스트로 연결하게 된다. 마치 이전 시간의 트리구조로 변형이 되는 것이다.
기존의 linked list의 병합은 끝원소를 찾아 연결하는 이유로 시간이 많이 소요됨에 반해 트리형태의 병합은 금방 이루어 질 수 있다.
각각의 셋은 root를 가진 트리구조를 표방하며 마지막원소는 각 트리의 ID이자 root가 된다.
배열을 통해 위의 구조를 다시 보자면 각 배열에 인덱스에 들어선 값들이 각 인덱스(노드)의 부모 노드가 누구인지를 알려주게 된다.
MakeSet과 Find의 순서와 Running time이고,
위와 같은 두개의 트리가 있을 때 이를 병합하는 방법은 두가지이다.
오른쪽 트리를 왼쪽트리로 병합시킬 수 있고 위와 같이 왼쪽트리를 오른쪽으로 병합할 수 있다.
이 때 병합할 시 트리의 높이가 낮은 편으로 병합을 하는 편이 유리하다. (이유는 복잡도가 낮아진다)
다시 한번 더 예시를 틀어주며 오른쪽 트리가 왼쪽트리보다 높이가 작으므로 오른쪽 병합 방식이 더 잘 되었다고 설명한다.
이번에는 Union 진행 시 Rank에 따라 하는 방법을 알아본다.
MakeSet 기능에 rank[i] <- 0 이라는 단계가 추가 되었다.
Union은 새롭게 rank를 비교하며 작동하도록 기능이 변경되었으며,
기본적인 성능은 크게 다르지 않음을 보여준다.
예시를 통해 다시 이해를 해보면 MakeSet으로 1~6까지의 원소를 추가하면,
각각이 자리를 잡게 되어 자기 자신이 부모가 되어 root가 된 것을 볼 수 있다.
이후 Union(2, 4)를 통해 2,4번 노드를 연결하는데,
이렇게 트리의 구성이 변경되고 2번 노드의 부모 노드가 4번으로 바뀐다. 이때 4번 노드의 rank도 1로 변경되었다.
또 다시 Union(5, 2)를 통해,
5번 노드도 4번 노드를 부모 노드로 삼고,
Union(3, 1)로 다시한번 변경이 되고,
Union(2, 3)을 통해,
1번 노드가 4번노드를 포함한 서브트리의 부모노드가 되었다. 동시에 rank도 2로 상승했다.
마지막으로 Union(2, 6)을 통해 6번 노드를 1번 노드 밑에 붙이게 된다.
어떤 노드 i에서든 rank[i]는 i의 트리의 높이와 동일하다 는 내용을 시사한다.
이번에는 Lemma라는 개념이 등장하며 어떤 트리의 높이든 최대 log2n이라고도 하며 또다른 내용으로는 k 높이를 가진 어떤 트리이든 최소 2^k만큼의 노드를 가진다고도 한다.
이에 대한 증명을 진행하며,
Union과 Find의 복잡도는 O(log n)이라며 정리한다.
마지막 개념으로 Path Compression에 대한 내용을 소개한다. 위의 트리에서 Find(6)를 통해 6번 노드부터 root까지 도달하는 길을 표시한 상태이다.
약간 다른 트리에서느 path가 더 짧은 것을 알 수 있는데 이를 path compression이라고 부른다.
이때 Find는 i가 root가 아니라면 해당 노드의 부모노드를 찾아 parent[i]로 다시금 업데이트 한다. 이런 과정을 통해 압축이 가능해지는 것 같다.
정의 상으로는 위와 같은 서술이 되며 바로 예시로 넘어가본다.
n개의 노드가 있을 때 이를 path compression한다면 이에 대해 각각은 log n의 계층으로 줄어드게 된다. 이 때 n의 최대값에 해당하는 것들에 log2를 취해보면 바로 위 계층의 최대값이 된다는 것을 간단히 알 수 있다.
다시 등장한 Lemma의 내용은 위와 같은 내용으로 바뀌었다.
해당 동작의 amortized time, 복잡도는 O(log n)이라고 한다. 실질적인 n값은 최대 5라고 한다. (2^65536값을 넘어가는 일은 거의 없으므로)
맨날똑같이다는이유가 귀찮아서가 아니라 정말 뭔말인지 모르겟어서그래💕💕
답글삭제