서론:

최근 재미있고 어려운 문제를 해결했는데, 그 문제에 쓰였던 기법이 상당히 특수한 경우에만 적용이 가능하긴 하지만 최소 한두번은 본 거 같아서 소개 드리려 가져왔습니다.

이분 탐색 응용 기법인데, 이미 이름이 있는 알고리즘인지는 모르겠네요. 본 기법을 소개하기 전에, 다음 문제를 어떤 방식으로 해결할 수 있을지 생각해보세요.

포커스 문제:

정점 N (N <= 1e18)개로 이루졌고, 정점 1이 루트인 트리가 주어진다. 각 정점엔 가중치가 주어지는데, 이 가중치는 자신의 부모의 가중치보다 크거나 같다. 또한, 각 정점의 자식들은 가중치 순으로 정렬되어 있다. 이 트리의 정점들 중에서 가장 작은 가중치를 가진 K (K <= 1e5)개의 정점들을 찾아라.

풀이:

N의 제한이 상당히 크기 때문에 트리를 완전히 탐색하기 어렵습니다. 어떤 식으로 탐색할 수 있을까요? 우선 모든 자식 노드는 부모 노드보다 가중치가 크기 때문에 루트부터 탐색해야 하는 사실은 자명합니다. 하지만 굉장히 큰 트리이기 때문에 어떠한 가중치에 도달 할때까지 탐색한 후엔 그만 돌아가야겠죠. 이 가중치를 너무 작게 설정하면 K개의 값을 미처 찾기도 전에 탐색을 종료하고, 너무 크면 최솟값을 찾지 않고 그냥 임의의 K개의 값을 찾겠죠. 그렇기 때문에 정확히 최솟값 K개를 찾을 가중치의 상한을 이분 탐색으로 찾을 수 있습니다. 

이제 x보다 작거나 같은 가중치를 가진 정점들의 수가 K보다 큰가?를 해결하는 결정문제로 바꾸었습니다. 이는 어떤 식으로 해결할 수 있을까요? 트리의 크기가 작지 않기 때문에 탐색을 하는것도 오래 걸릴 거 같지만 실은 그냥 나이브하게 탐색을 진행해도, K개의 정점을 찾는 순간 탐색을 종료하기만 하면 O(K)에 탐색을 마칠 수 있습니다. 이 시간복잡도는 쉽게 설명이 가능합니다. 한번 탐색을 진행할때마다 찾은 x 이하의 정점은 하나 늘어나기 때문에 D번 총 탐색하고, 각 탐색중 불필요하게 반복하는 연산은 최대 1번–자식들을 순회하는 작업 중 자식의 가중치가 x 이상인 경우–이기 때문에 O(K)에 결정문제를 해결 할 수 있습니다. 

이분탐색을 진행하기 때문에 O(K log X)에 전체문제를 해결 할 수 있습니다. 

결론:

이러한 풀이는 일반화하기 쉬워요. 탐색 범위가 굉장히 크지만 실제로 찾아야 하는 도착점이 작다면 쉽게 적용되는 기법이죠. 밑에 쉬운 문제부터 어려운 순으로 연습 문제 몇개를 소개할게요.

연습 문제:

https://www.acmicpc.net/problem/21788

https://www.acmicpc.net/problem/14166

https://www.acmicpc.net/problem/19616