Algorithm/LCA
-
Lowest common ancestor(LCA)Algorithm/LCA 2020. 3. 23. 10:46
LCA 트리에서 서로 다른 두 노드에 대해 루트노드에서 가장 멀리 있는 공통 조상을 LCA라고 합니다. 위의 그림에서 검은색 노드의 LCA는 빨간색 입니다. LCA를 찾는 방법은 1. 두 노드의 dept를 맞춘다. 2. 두 노드가 같아질때까지 계속 위로 올라간다. 2단계롤 나눌수 있습니다. 가장 쉽게 구현할수 있는 방법은 하나씩 올라가는 것입니다. 이 경우엔 최악의 경우 O(n)의 시간 복잡도를 가지게 됩니다. 더 빠르게 구현하기 위해서 '희소테이블' 이라는 테크닉을 이용할 수 있습니다. 즉 하나씩 올라가는 것이 아니라 가능한 최대한 멀리 올라가는 것이지요. 예를들어 두 노드 A, B의 LCA인 C노드의 깊이가 3이고 A의 깊이는 100, B의 깊이는 200 이라고 하면, 하나씩 올라가는것은 너무 정직하..