알고리즘 스터디 19일차

목차

1. 최소 공통 조상 (LCA)

2. LCA 응용 - 빠르게 구하기

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

 

1. 최소 공통 조상 (LCA)

트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드

 

일반적인 최소 공통 조상 구하기 : 트리의 높이가 크지 않을 때 (시간제한의 제약이 없을 때)

루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장, 탐색은 DFS 혹은 BFS로 진행 (4번,15번 노드의 최소 공통 조상을 구하는 과정)

 

선택된 두 노드의 깊이가 다른경우는 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춤 이때 두 노드가 같다면 해당 노드가 최소 공통 조상 ( 따라서 탐색 종료)

 

깊이가 같은 상태에서 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복

 

 

2. LCA 응용 - 빠르게 구하기

일반적인 LCA는 한칸씩 노드를 올려가면서 확인했지만 빠르게 구하기는 2^k 씩 올라가 비교한다.

따라서 기존에 자신의 부모노드만 저장해 높던 방식에서 2^k번째 위치의 부모 노드까지 저장.

 

부모 노드 배열의 정의 : k[K][N] = N번 노드의 2^k 번째 부모의 노드 번호

부모 노드 배열의 점화식 : P[K][N] = P[K-1][P[K-1][N]]

부모 노드 배열의 점화식으로 값 채우기

 

14의 2²번째, 즉 4번째 부모 노드(P[2][14])를 구하기

선택된 두 노드의 깊이 맞추기 (위의 배열을 이용하여 깊이를 2^k 단위로 넘어가면서 맞춤)

최소 공통 조상 찾기

노드 10,11이 다른 노드이기 때문에 바로 위 노드 P[0][10] 또는 P[0][11]이 노드6의 최소 공통 조상