https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 사용한 알고리즘 : LCA(Lowest Common Ancestor, 최소 공통 조상) 풀이 전략 위 문제에서 주어진 첫 번째 입력을 그래프로 나타내면 아래와 같다. 문제에서는 16과 7의 가장 가까운 공통 조상인 LCA를 구하라고 주어졌다. 결론부터 말하면 눈에 보이듯 4인데, 이를 알고리즘적으로 어떻게 구할 수 있을지 생각해보자. 먼저 LCA..
