[2021/09/13][짤막한 이야기 - 최소 공통 조상]

[2021/09/13][짤막한 이야기 - 최소 공통 조상]
"최소 공통 조상(Lowest Common Ancestor, LCA)"이란 임의의 트리가 있을 때, 두 노드의 공통된 조상을 찾는 문제이다.
예를 들어 그림에서의 2와 6의 LCA는 1이고, 2와 5의 LCA는 2이다.
공통된 조상 중 가장 깊이가 깊은 조상을 찾으면 되는 문제로, 자기 자신이 최소 공통 조상의 답으로 도출될 수도 있다.
임의의 트리에서 수행되는 알고리즘이기 때문에, 알고리즘 수행 대상인 두 노드가 서로 다른 깊이에서 시작할 수 있다.
이 경우 같은 깊이가 될 때까지 깊은 쪽을 위로 올려주는 과정이 필요하다.
예를 들어 그림에서의 2와 6의 LCA를 찾기 위해서는 6을 4의 위치로 이동하여 깊이를 보정한다.
그 다음 두 노드의 값이 일치(공통)할 때 까지 위로 올라가는 과정을 수행하면 된다.
중요한 점은 트리의 깊이가 매우 깊을 경우 공통된 조상을 찾기 위하여 위로 올라가는 횟수도 매우 많아진다는 점이다.
이 경우 이진 팀색(Binary Search)에서의 아이디어를 유사하게 활용하여 깊이 보정 및 공통 조상 탐색 과정을 효율적으로 수행할 수 있다. 
#이야기 #루니프 #알고리즘 #자료구조 #최소공통조상 #LCA #트리 #노드 #이진탐색

[2021/09/13][Short Story - Lowest Common Ancestor]
"Lowest Common Ancestor (LCA)" is the problem of finding the common ancestor of two nodes when there is an arbitrary tree.
For example, the LCA of 2 and 6 in the figure is 1, and the LCA of 2 and 5 in the figure is 2.
It is a problem that only needs to find the deepest ancestor among common ancestors, and it can be derived by itself as the answer of the lowest common ancestor.
Since it is an algorithm that is executed in an arbitrary tree, two nodes that are the target of the algorithm can start at different depths.
In this case, it is necessary to raise the deep node up until it reaches the same depth.
For example, to find the LCA of 2 and 6 in the figure, move 6 to the position of 4 for correcting the depth.
Then, the process of moving upwards is performed until the values ​​of the two nodes match (common).
The important point is that if the tree is very deep, the number of times it goes up to find a common ancestor is very high.
In this case, the depth correction and common ancestor search process can be efficiently performed by similarly utilizing the ideas from the binary search.
#Story #LootNiP #Algorithm #DataStructure #LowestCommonAncestor #LCA #Tree #Node #BinarySearch