LCA (최소 공통 조상) 알고리즘
LCA 알고리즘이란? 2개의 노드가 주어질 경우, 해당 노드들의 공통된 조상 중 가장 깊이가 깊은 노드를 조회하는 알고리즘이다. 대략적인 순서는 다음과 같다. 1. 모든 노드에 대해 깊이를 계산한다. 2. 최소 공통 조상을 조회할 두개의 노드를 확인한다. 3. 해당 노드들의 깊이를 똑같이 맞춰준다. 4. 부모 노드를 한단계씩 거슬러 올라간다. 5. 하나의 노드에서 만날 때 나온 값 출력 코드는 다음과 같다. (백준 11437 문제 참고) import sys # 깊이 계산 함수 def dfs(node, depth): check_nod[node] = 1 depth_nod[node] = depth for i in tree_nod[node]: if check_nod[i] == 1: continue parent_..
프로그래밍/코테 준비
2024. 2. 29. 01:57