common1 LCA (Lowest Common Ancestor) LCA는 이름에서 알 수 있듯이 두 정점 A와 B에서 가장 가까운 공통된 조상을 찾는 알고리즘입니다. 여기에는 2 가지 방법이 있는데요, 하나씩 조상 노드를 살펴보는 방법과 DP를 사용하는 방법이 있습니다. 트리의 depth를 H라고 할 때, 조상 노드를 하나씩 살펴보는 방법으로는 보통 시간복잡도가 O(H)가 나오지만, 최악의 경우 O(N)이 걸릴 수 있습니다. 하지만 DP를 사용하게 된다면? 보통 O(log H)가 걸리지만, 최악의 경우 O(log N)이 걸립니다. DP를 사용하는게 훨씬 빠르죠? 그래서 노드의 개수가 매우 많고, 검사해야할 노드가 매우 많은 경우에 DP를 사용한 방법을 활용하면 빠르게 답을 찾을 수 있습니다! 먼저, 조상 노드를 하나씩 살펴보는 방법은 사실 간단해요. 두 정점 A와 B.. 2021. 4. 1. 이전 1 다음
