최소 공통 조상 알고리즘 (1) 썸네일형 리스트형 [백준]11437 LCA(Python) https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 접근 LCA(Lowest Common Ancestor): 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 ♣ 동작 방식 모든 노드에 대한 깊이(depth)를 계산한다. 최소 공통 조상을 찾을 두 노드를 확인한다. 먼저 두 노드의 깊이가 동일하도록 거슬러 올라간다. (첫 번째 while문) 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. (두 번째 .. 이전 1 다음
