알고리즘 문제 풀이 노트: 트리 탐색, 선형 기반, 그리고 순열 최적화
CF1534H - 루트 탐색 최적화트리에서 두 노드 a, b를 찾기 위한 최소 질의 횟수를 분석한다. 루트 r를 고정했을 때, 각 노드 u에 대해 서브트리 내에서 탐색하는 최악의 비용 cost[u]를 정의한다.잎 노드의 경우 확인 비용은 1이다. 내부 노드에서는 자식들을 cost 기준 내림차순으로 정렬하여 탐색하며, i번째 자식을 탐색할 때의 비용은 cost[child_i] + i - 1이 된다. ...
6월 29일 01:05에 게시됨