LCA(알고리즘)

1. 개요[편집]

---

LCA(최소공통조상)은 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다.

LCA는 Lowest Common Ancestor의 약자로 최소공통조상 이라는 뜻을 가지고 있다. 쉽게 말하자면 두 정점에서 (자신을 포함한)조상들을 거슬러 올라갈 때 처음으로 공통되게 만나는 정점을 지칭한다. 트리에서 쓰이는 알고리즘이다.