728x90 반응형 DP1 최소 공통 조상 (Lowest Common Ancestor, LCA) 최소 공통 조상 (LCA) 알고리즘Problem Setup$N$개의 node로 이루어진 트리가 주어진다. (트리이므로 간선의 개수는 $N-1$개이다)$q$개의 query에 대하여 두 node사이의 거리를 계산한다. 위 그림은 백준 11437 LCA 문제이다. 1번 노드가 루트이다.6번과 11번 노드의 최소 공통 조상은 2번 노드이다. (1번 노드 역시 공통 조상이지만, 최소가 아니다.)10번과 9번 노드의 최소 공통 조상은 4번이다. 즉, LCA(10, 9) = 48번과 15번 노드의 최소 공통 조상은 1번이다. 즉, LCA(8, 15) - 1 루트노드에서 DFS/BFS 알고리즘을 통해 각 노드의 깊이를 계산하여 depth 배열에 저장한다.1의 depth는 0, 2와 3의 depth는 1, 4번~8번 노.. 2024. 7. 11. 이전 1 다음 728x90 반응형
