[2021/09/14][짤막한 이야기 - 최소 공통 조상(개선)]

[2021/09/14][짤막한 이야기 - 최소 공통 조상(개선)]
※ 해당 포스트는 분량 관계상 영문 버전이 제공되지 않습니다.
최소 공통 조상(LCA) 알고리즘은 “두 노드의 깊이 맞추기”와 “두 노드의 조상 맞추기”로 수행된다.
두 과정 모두 자신보다 위에 존재하는 노드로 올라가게 되는데, 트리의 높이가 매우 높다면 이 과정에서 많은 시간이 소요된다.
총 높이가 1,000,000인 트리에서 깊이도 1,000,000인 두 노드의 공통 조상을 찾는다고 생각해보자.
공교롭게도 공통 조상이 “루트(Root)”인 경우에는 1,000,000번을 올라가야 한다.
즉, 높이가 H인 트리에서의 최소 공통 조상 찾기 알고리즘은 시간 복잡도가 O(H)에 해당한다.
이를 개선하기 위해서는 높이를 1칸씩 올라가는 것이 아니라 2^K칸씩 올라가면 된다.
깊이 맞추기의 경우, 깊이가 더 깊은 쪽의 노드가 2^K칸 올라갔을 때 다른 노드를 추월했다면, 취소하고 2^(K-1)칸을 올라간다.
조상 맞추기의 경우, 깊이 맞추기가 완료된 두 노드가 2^K칸 올라갔을 때 이미 공통 노드를 가리키고 있다면, 취소하고 2^(K-1)칸을 올라간다.
예를 들어, 그림에서 10과 4의 LCA를 구할 때,
깊이 맞추기에서는 10을 2^2칸만큼 올리면 1에 도착한다.
그러면 이미 4보다 위로 추월했기 때문에 이를 취소하고 10으로 되돌아간다.
10에서 다시 2^1칸만큼 올려서 5에 도착한 후 2^0칸만큼 더 올려서 2에 도착하면 된다.
조상 맞추기의 경우 2와 4의 두 노드가 2^0칸만큼 올라가면 이미 1로 공통 노드를 가리키고 있다.
그러므로 취소하고 그대로 알고리즘을 종료한다.
이 때의 최소 공통 조상은 2의 부모(혹은 4의 부모)인 1이 된다.
수행했던 “맞추기” 과정을 취소하고 다시 더 짧게 올라가야 할 수 있다는 점에서 시간낭비인 것 같지만, 전체적인 시간 복잡도는 O(logH)가 된다.
이는 이진 탐색에서처럼 반씩 나누어서 올라가는 효과를 가지기 때문이다.
#이야기 #루니프 #알고리즘 #자료구조 #최소공통조상 #LCA #트리 #노드 #이진탐색

[2021/09/14][Short Story - Lowest Common Ancestor(Improvement)]
※ The English version of this post is not provided due to the length of the post.
#Story #LootNiP #Algorithm #DataStructure #LowestCommonAncestor #LCA #Tree #Node #BinarySearch