LCA(Lowest Common Ancestor) 알고리즘
오늘은 LCA(Lowest Common Ancestor) 알고리즘에 대해 다뤄보겠습니다. LCA 알고리즘이란? 제목에서 보시다시피, 최소 공통 조상 알고리즘입니다. 우선, 아래 그림을 통해 이 알고리즘을 이해해보도록 합시다. 깊이(Depth)란? 이와 같은 트리가 있다고 할 때, 1이란 값을 가진 Node는 루트(Root)노드라고 불립니다. 루트(Root)노드는 깊이(Depth)가 0이며, 루트를 기준으로 아래부터 1, 2, 3, .. 이런 방식으로 깊이(Depth)가 증가하게 됩니다. 그럼, 노드 9는 깊이가 3, 노드 8의 깊이도 3, 노드 7의 깊이는 2라는 사실을 알 수 있습니다. 조상(Ancestor)이란? Depth에 대한 설명을 모두 마쳤으니, 이제 조상(Ancestor)에 대한 이야기를 해..
