728x90
반응형
최소 공통 조상 LCA (Lowest Common Ancestor)
임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드 탐색 시 처음 공통으로 만나게 되는 부모노드
- BFS, DFS 사용
- 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올리면서 같은 길이로 맞춤
(이때 두 노드가 같으면 탐색 종료)
최소 공통 조상 빠르게 구하기
서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때
(2**k) 씩 올라가 비교하느 방식 -> (2**k)번쨰 위치의 부모 노드까지 저장해야 함
1. 부모 노드 저장 리스트 만들기
정의: P[k][n] = n번 노드의 (2**k)번쨰 부모 노드 번호
점화식: P[k][n] = P[k-1]P[[k-1][n]]
- n의 (2**k)번째 부모 노드 = n의 (2**(k-1))번째 부모노드의 (2**(k-1))번쨰 부모노드
- k는 트리의 깊이 > (2**k)를 만족하는 최대값
2. 선택된 두 노드의 깊이 맞추기
3. 최소 공통 조상 찾기
반응형
