알고리즘 #Algorithm #LCA
-
[알고리즘 소개] Tree Algorithm - 최소 공통 조상(LCA, Lowest Common Ancestor)Computer - Problem Solving/Algorithm 2022. 9. 29. 18:57
어느 정도 수준있는 문제에서 많이 쓰이는 문제이다. 이 알고리즘이 메인이 된다기보다는, 다른 알고리즘(Tree DP 등등)과 짬뽕해서 조미료로 쓰이는 경우가 굉장히 많다. 최소 공통 조상이란? 다음과 같이 루트(위 그림에서 1번)가 있는 트리가 있을 때, LCP(a,b)는 a와 b를 모두 자식으로 가지는 노드들 중에서 a와 b에 가장 거리가 짧은 조상을 말한다. 예를 들어 LCP(7,9)=2, LCP(10,12)=6, LCP(7,10)=1이 된다. a가 b의 조상인 경우, 혹은 그 역인 경우 LCP의 값이 a 혹은 b가 될 수 있다(ex. LCP(7,1)=1) 일반적으로 LCP(a,b)의 쿼리가 Q개 있는 경우 DFS, BFS 등 일반적인 Search Algorithm을 사용하면 O(NQ)가 걸릴 것이다..