최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 기존에 자신의 부모 노드만 저장해 놓던 방식에서 2ᵏ번째 위치의 부모 노드까지 저장해 둬야함 원리 1. 부모 노드 저장 리스트 만들기 부모 노드 리스트 정의 : P[K][N] = N번 노드의 2ᵏ 번째 부모의 노드 번호 내 바로 위에 있는 부모 노드뿐만 아니라, 내 자리에서 2ᵏ 칸 위에 있는 부모가 누군지 저장해놔야함 부모 노드 리스트의 점화식 : P[K][N] = P[K-1][P[k-1][N]] 예시) K = 2 N=12 가정 P[2][12] = P[1][P[1][12]] P[2][12] : 12번 노드의 2²번째 부모 = 1 P[1][12] = 12번 노드의..