[알고리즘] 최소 공통 조상 - LCA(Lowest Common Acestor)
2020.09.10
1. LCA (Lowest Common Acestor) 알고리즘이란? 트리 구조에서 최소 공통 조상을 찾는 알고리즘으로, 두 정점 (u, v)에서 가장 가까운 공통 조상을 찾는 알고리즘입니다. 아래와 같은 트리가 있다고 해보겠습니다. (u, v)의 조상을 LCA(u, v)라고 하면, LCA(2, 7)은 무엇일까요? 🤔 몇 번 더해보겠습니다. LCA(9, 6)은 무엇일까요? 마지막으로, LCA(12, 14)는 무엇일까요? LCA(12, 14) = LCA(14, 12) = 12 라는걸 알 수 있습니다. 최소 공통 조상이라는게 무엇인지 이해되셨나요? 🙂 2. LCA 알고리즘 동작 과정 우선 가장 먼저 해야할 건 당연히 입력받은 정점과 간선으로 트리를 구성하는 것입니다. 다음으로, depth와 조상 노드를 같이..