알고리즘 & 자료구조/LCA
최소 공통 조상(LCA)
문제 https://www.acmicpc.net/problem/11438 개요 트리의 최소 공통 조상이란 Lowest Common Ancestor을 의미하며 LCA로 알려져 있다. 예를 들어 위와 같은 트리에서는 LCA(2, 3) = 1 LCA(6, 7) = 1 LCA(15, 11) = 11 이다. 풀이 LCA를 찾는 방법은 Linear하게 \(O(N)\)만에 찾는 방법과 \(O(logN)\)만에 찾는 방법이 있다. 물론 노드의 개수가 많으면 많을 수록 \(O(logN)\)을 쓰는 것이 훨씬 효율적이고 그 방법을 써야만 한다. 이 글은 \(O(logN)\)만에 찾는 방법을 설명하는 것에 중점을 둔 글이므로 Linear하게 찾는 방법은 간단히 설명하고 넘어가겠다. LCA를 찾는 Linear한 방법 : 1...