728x90 반응형 Lowest Common Ancestor1 알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) 알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라 갈 때 처음 공통으로 만나게 되는 정점이다. 정점 A혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다. 8과 9의 공통 조상들은 1, 2, 4 / 8과 9의 최소 공통 조상은 4 3과 6의 공통 조상들은 1, 3 / 3과 6의 최소 공통 조상은 3 8과 5의 공통 조상들은 1, 2 / 8과 5의 최소 공통 조상은 2 [ 최소 공통 조상 구하기 ] - 최상위 조상 정점을 시작으로 DFS 혹은 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. - 정점의 부모를 따라 하나씩 올라가 LCA를 찾는다. 시간복잡도 : 트리의 깊이.. 2021. 2. 3. 이전 1 다음 728x90 반응형
