[알고리즘] LCA(최소 공통 조상) (c++)
LCA(Lowest Common Ancestor)란?LCA 알고리즘은 임의의 두 정점(u, v)에서 가장 가까운 공통 조상을 찾는 알고리즘이다. 아래 예시를 보면 쉽게 이해할 수 있을 것이다. 위와 같은 트리가 있을때 14, 16 정점의 LCA는 정점 1이다. 정점 14의 조상 정점들은 순서대로 9, 5, 2, 1이 있다. 정점 16의 조상 정점들은 순서대로 12 7, 3, 1이 있다.정점 14, 16이 함께 공유하는 가장 가까운 조상은 정점 1이 된다. 정점 8, 14의 LCA를 구하면 정점 2가 된다. 정점 8의 조상 정점들은 순서대로 4, 2, 1이 있다. 정점 14의 조상 정점들은 순서대로 9, 5, 2, 1이 있다.정점 8, 14이 함께 공유하는 가장 가까운 조상은 정점 2가 된다. 이번엔 정..
