알고리즘/그래프
2020. 5. 11.
최소 공통 조상
최소 공통 조상(Least Common Ancestor, LCA)는 트리에 있는 정점 \(u, v\)에 대해, \(u\)와 \(v\)의 공통 조상 중 가장 가까운 것을 말합니다. 예를 들어 아래와 같은 트리에서, 2번 정점과 7번 정점의 LCA는 1번 정점, 9번 정점과 4번 정점의 LCA는 2번 정점입니다. 그러면 LCA를 구하는 알고리즘에 대해 알아봅시다. 1. \(O(n)\) Navie https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. www.a..
