2021/03/28

[Algorithm] LCA 알고리즘

LCA는 "Lowest Common Ancestor" 가장 가까운 공통 조상을 찾는 알고리즘이다. 백준 3584번을 풀면서 이해해보장 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 해당 트리에서 3번과 2번의 가장 가까운 공통 조상은 10번이라는 것을 바로 알 수 있다. 그렇다면 a와b가 주어졌을 때 알고리즘으로 최소 공통 조상을 찾아보자. Rule 📌 a의 조상을 모두 찾아 리스트로 만든다. 📌 b의 조..