① 서로의 깊이를 맞추거나, ②같아지는 노드를 찾을 때, 기존 한단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 → 기존 자신의 부모노드만 저장해 놓던 방식에서 2ᵏ 번째 위치의 부모노드까지 저장해 둬야한다. (미리 배열로 저장해야 탐색이 가능하다.) Step 01) 부모노드 저장 배열 만들기 점화식 활용 부모노드 배열 정의 P[K][N] = N번 노드의 2ᵏ 번째 부모의 노드번호 → P[2][13] = 노드 13의 2² 번째 부모노드 점화식 (동적계획법) P[K][N] = P[K-1][ P[K-1][N] ] → P[2][13] = P[1][ P[1][13] ] 점화식에서 N의 2ᵏ 번째 부모노드는 N의 2ᵏ⁻¹번째 부모노드의 2ᵏ⁻¹번째 라는 의미 즉, k=4라고 가정한다면 K의 16번째 부모노드..
