카테고리 없음
LCA(Lowest Common Ancestor) 최소 공통 조상
skesswswkk
2020. 9. 24. 03:33
[개념]
LCA(Lowest Common Ancestor) 알고리즘
LCA(Lowest Common Ancestor) 알고리즘이란? LCA 알고리즘이란 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다. 예를들어
www.crocus.co.kr
[과정]
[예제]
https://www.acmicpc.net/problem/11438
[Algorithm] 최소 공통 조상 LCA (Lowest Common Ancestor)
최소 공통 조상이란? 최소 공통 조상(LCA)란 두 노드가 트리에서 두 노드를 포함하여 조상을 따라 거슬러 올라갈때 처음 공통으로 만나게 되는 정점이다. 아래 그림에서 5와 8의 LCA 는 바로 1이다.
matice.tistory.com