최소공통조상

최소 공통 조상(Lowest Common Ancestor)

최소 공통 조상(LCA)란? LCA란 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v거나 v의 조상인 노드들 중 가장 깊은 노드이다 예를들어, 아래의 트리에서 노드 4와 3의 LCA는 1번 노드이다 다른 예로는 노드 9, 14의 LCA는 2번 노드이며, 노드 3, 13의 LCA는 3번 노드이다 여기서 한가지 사실을 알 수 있는데 노드 u,v와 이들의 LCA w의 관계이다 u,v의 최단 경로는 u-w-v 형태라는 것이다 이를 아래의 트리에서 빨간 경로로 확인할 수 있다 따라서, 트리 문제에서 최단경로를 빠르게 찾길 원한다면 가장먼저 LCA를 생각해봐야 한다 LCA 구현 방법 1. 노드 u,v 가 서로 만날때까지 부모노드를 따라서 두 노드를 옮겨 보는 방법 : 선형 탐색 두..