LCA(Lowest Common Ancestor) 알고리즘 AKA. 최소 공통 조상 알고리즘 요약 : 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘이다. 구현법 : 일반적으로 DFS를 활용해 구현한다. 다이나믹 프로그래밍(DP), 세그먼트 트리를 활용해 시간 복잡도를 개선할 수 있다. (1) 모든 노드에 대한 깊이(depth)를 계산한다. (2) 최소 공통 조상을 찾을 두 노드를 확인한다. (2)-(1) 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다. = 같은 라인에 위치할때까지 올라간다. (2)-(2) 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. (3) 모든 LCA(a,b) 연산에 대하여 2번의 과정을 반복한다. 기본 구현 코드 /..
