최소 공통 조상1 [C/C++] 백준 #1761 정점들의 거리(최소 공통 조상) 트리에서 두 노드간 최소 거리를 구하는 방법은 여러가지가 있습니다. 가장 간단하게 생각할 수 있는 것은 깊이 우선 탐색(DFS) 이용하는 방법이 있겠죠. 하지만, 노드의 수가 많다면, 꽤 오랜 시간이 걸리겠지만, 크게 문제가 되지 않습니다. 노드의 개수가 N개라면, \(O(N)\) 알고리증으로 풀 수 있으니까요. 물론 재귀 호출의 깊이가 깊어지기 때문에 너비 우선 탐색(BFS)를 이용할 수도 있습니다. 하지만, 이번 문제는 단순하게 두 노드간의 거리를 한번 구하는 것이 아니고 M번 구하는 것입니다. 그러면, 알고리즘 효율이 \(O(NM)\)이 됩니다. 그렇기 때문에 보다 효율적인 알고리즘을 찾아야 합니다. 최소 공통 조상 알고리즘은 기본적으로 많은 질의(query)가 있는 경우 사용할 수 있습니다. 모든.. 2022. 10. 11. 이전 1 다음
