[알고리즘] LCA(Lowest Common Ancestor)

[알고리즘] LCA(Lowest Common Ancestor) 최소 공통 조상을 찾는 알고리즘 → 두 정점이 만나는 최초 부모 정점을 찾는 것! 트리 형식이 아래와 같이 주어졌다고 하자 4와 5의 LCA는? → 4와 5의 첫 부모 정점은 '2' 4와 6의 LCA는? → 첫 부모 정점은 root인 '1' 어떻게 찾죠? 해당 정점의 depth와 parent를 저장해두는 방식이다. 현재 그림에서의 depth는 아래와 같을 것이다. [depth : 정점] 0 → 1(root 정점) 1 → 2, 3 2 → 4, 5, 6, 7 parent는 정점마다 가지는 부모 정점을 저장해둔다. 위의 예시에서 저장된 parent 배열은 아래와 같다. // 1 ~ 7번 정점 (root는 부모가 없기 때문에 0) int parent..