정답에 대한 이진 탐색

때로는 답을 직접 계산할 수 없지만 추측을 확인할 수는 있습니다. 답에 대해 이진 탐색을 하면 어려운 최적화 문제가 쉬운 검사 문제로 바뀝니다.

가능 여부가 단조일 때 작동합니다. 어떤 값이 가능하면 그보다 큰 값이나 작은 값도 모두 가능해야 합니다. 탐색하는 것은 바로 그 순서입니다.

가능한 답 중 가장 작은 값과 가장 큰 값을 low와 high로 정하세요. 최소 용량 문제에서는 low가 원소 하나의 크기이고 high가 전체 합입니다.

이 방법의 핵심은 추측한 X가 가능한 경우 true를 반환하는 can(X) 함수입니다. 이 함수는 보통 선형 시간에 실행됩니다.

하루 처리 용량 cap이 주어지면 매일 탐욕적으로 항목을 채우고 필요한 날 수를 세세요. 날 수가 제한 D 이내로 유지될 때 can(cap)은 true입니다.

조건을 통과하는 가장 작은 cap을 찾아야 합니다. 이는 용량에 대한 첫 true 탐색이므로 high = mid 템플릿을 재사용하세요.

can(mid)가 true라면 더 작은 용량도 가능할 수 있으므로 high = mid로 설정하세요. 그렇지 않으면 low = mid + 1로 하한을 높이세요.

총 비용은 O(검사 횟수 × 로그 범위)입니다. 범위가 10억만큼 넓어도 선형 검사는 약 30번뿐이므로 엄격한 제한에서도 충분히 빠릅니다.

가장 큰 가능 값을 찾으려면 논리를 뒤집어 마지막 true를 탐색하세요. 가능하면 low를 올리고, 불가능하면 high를 줄입니다.

실수형 답을 구할 때는 정수 mid 대신 100번처럼 정해진 횟수만큼 반복하세요. 매번 구간이 절반으로 줄어들어 매우 높은 정밀도에 빠르게 도달합니다.

최소 중 최대, 최대 중 최소, 또는 가능한 가장 작은 k 같은 표현은 답에 대해 이진 탐색하라는 신호입니다. 이런 표현을 알아보는 감각을 기르세요.

답에 대한 이진 탐색을 언제 적용할 수 있는지 판단해 보세요.

이제 답의 범위를 정하고 가능 여부 검사를 작성하여 최솟값이나 최댓값을 이진 탐색할 수 있습니다. 어려운 문제도 추측하고 검증하는 문제로 바뀝니다. 🏆