LCA2 썸네일형 리스트형 18. 최소 공통 조상 (LCA: Lowest Common Ancestor) 2 앞에서 최소 공통 조상(이하 LCA) 알고리즘을 통해 트리 내 두 노드의 공통 조상을 찾는 방법을 설명드린 적이 있었습니다. 트리 내 두 노드의 가장 가까운 조상을 찾는 LCA 알고리즘을 통하여 노드가 공유하는 조상 노드 중 가장 깊은 노드를 찾는 방법을 알게 되었습니다. 가장 원초적 형태의 LCA 알고리즘도 물론 강력한 기능을 갖고 있는 알고리즘이지만 이를 강화시킨 버전의 LCA 알고리즘을 이번 챕터에서 말씀드리려고 합니다. 크기가 그렇게 크지 않은 트리에서는 특정 노드에서 조상을 찾기 위해 올라가는 과정이 그렇게 멀지 않습니다. 두 노드를 비교하여 깊이가 더 깊은 노드의 깊이를 상대적으로 깊이가 얕은 노드에 맞춰주고, 부모로 올라가는 과정을 몇 번 거치면 쉽게 LCA를 구할 수 있었습니다. 문제가 되.. 이전 1 다음
