LCA

[백준] 3584. 가장 가까운 공통 조상 - Python

[Gold IV] https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 처음 보는 LCA (Lowest Common Ancestor) 문제. DFS를 통해 Root 노드부터 각 노드의 깊이(depth)를 저장하고, 입력된 두 노드의 depth를 맞춘 후, 공통 조상이 나올 때까지 그대로 거슬러 올라가는 식으로 해결하였다. 이 풀이의 경우 O(N)의 Time Complexity로 해결한 경우이며..