정리하기 위한 블로그 정리하기 위한 블로그

LCA 구현하는 과정을 최대한 간단하게 정리해본다. LCA 는 가장 가까운 공통 조상을 찾는 알고리즘인데, 두 노드에서 한 칸씩 이동하며 찾을 수도 있지만 2의 n제곱 칸씩 이동하며 찾는 방법도 가능하여 시간을 많이 단축할 수 있다. 먼저 필요한 자료구조는 다음과 같다. - depth[node] : node의 루트 노드로부터의 깊이, lca에서 두 노드의 깊이 차이를 구할 때 필요 - parent[node][k] : node의 2^k 번째 부모의 노드 번호, lca에서 두 노드의 공통 조상을 찾을 때 필요 과정은 다음과 같다. 1. dfs() 로 depth[node] 와 parent[node][0] (직계 부모)를 구한다. 2. build() 로 parent[node][1..maxlog] 를 구한다. k..