DailyStudyNote

최소 공통 조상(Lowest Common Ancestor, LCA) 최소 공통 조상(Lowest Common Ancestor, LCA) 란? 최소 공통 조상(LCA) 란 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘 이다. 즉 두 정점이 만나는 최초 부모 정점을 찾는 것을 의미한다. 최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘 모든 노드에 대한 깊이(Depth)를 계산한다. 최소 공통 조상을 찾을 두 노드를 확인한다. 먼저 두 노드의 깊이(Depth)가 동일 하도록 거슬러 올라간다. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. 최소 공통 조상을 찾을 두 노드를 확인한다. LCA 알고리즘 풀이 이해 1. 각 노드의 "D..