LCA (최소공통조상) 알고리즘 완벽 가이드
LCA (Lowest Common Ancestor)
LCA(최소공통조상)는 트리에서 두 정점의 가장 가까운 공통 조상을 찾는 문제이다. 트리 관련 알고리즘에서 가장基础的인 개념 중 하나이다.
1. 브루트 포스 방식
가장 간단한 접근법은 직접 위로 올라가며 찾는 것이다. 먼저 각 정점의 깊이(depth)와 부모 정보(fa)를 전처리한다.
알고리즘:
두 정점 u, v 중 더 깊은 정점을 찾는다.
...
7월 17일 22:27에 게시됨