답에 대한 이진 탐색

이 글에서는 몇 가지 문제를 예로 들어 이진 탐색의 중요한 변형인 답에 대한 이진 탐색을 살펴봅니다. 이는 문제를 「어떤 쉽게 계산할 수 있는 $x$에 대한 성질이 성립하는 최대의 $x$를 찾으십시오」와 같은 형태로 정식화한 뒤, 이 $x$를 이진 탐색으로 찾는 방법입니다.

#«외양간의 소들»

직선 위에 $n$개의 외양간이 있으며(직선 위의 좌표가 주어집니다), 여기에 $k$마리의 소를 소들 사이의 최소 거리가 가능한 한 커지도록 배치해야 합니다.

$1 < k < n$임이 보장됩니다.

문제를 정면으로 풀려고 하면 무엇을 해야 할지 전혀 알 수 없습니다. 대신 더 간단한 문제를 풀어 봅시다. 소들을 그보다 가깝게 배치할 수 없는 거리 $x$를 우리가 알고 있다고 가정합시다. 그렇다면 우리는 소들 자체를 배치할 수 있겠습니까?

답은 ‘그렇다’이며, 게다가 꽤 간단합니다. 첫 번째 소는 가장 왼쪽 외양간에 넣습니다. 그렇게 하는 것이 항상 유리하기 때문입니다. 그다음 몇 개의 외양간은 거리가 $x$보다 작다면 비워 두어야 하고, 남은 외양간 중 가장 왼쪽 외양간에 두 번째 소를 넣어야 하며, 이와 같이 계속합니다.

구현 방법은 다음과 같습니다. 정렬된 외양간 배열을 왼쪽에서 오른쪽으로 순회하면서 마지막 소의 좌표를 저장하고, 이전 소까지의 거리에 따라 외양간을 건너뛰거나 그 외양간에 새 소를 넣으면 됩니다.

bool check(int x) {
    int cows = 1;
    int last_cow = coords[0];
    for (int c : coords) {
        if (c - last_cow >= x) {
            cows++;
            last_cow = c;
        }
    }
    return cows >= k;
}

이러한 그리디 알고리즘이 끝났을 때 안전한 마구간보다 소가 먼저 바닥났다면 답은 확실히 $x$ 이상이고, 그렇게 하지 못했다면 답은 확실히 $x$보다 작습니다.

이제 $x$를 전부 시도해 보면서 $O(n)$짜리 검사를 $X = \frac{\max x_i - \min x_i}{k}$번 수행할 수 있지만, 이보다 더 빠르게 할 수도 있습니다.

$x$에 대해 이진 탐색을 실행합시다. 어떤 작은 $x$에 대해서는 소들을 확실히 배치할 수 있지만, 어떤 큰 값부터는 더 이상 배치할 수 없으며, 문제에서 찾으라고 요구하는 것이 바로 이 경계이기 때문입니다.

int solve() {
    sort(coords.begin(), coords.end());
    int l = 0; // так как коров меньше, чем стойл, x = 0 нам всегда хватит
    // по условию есть хотя бы 2 коровы,
    // которых мы в лучшем случае отправим в противоположные стойла:
    int r = coords.back() - coords[0] + 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (check(m))
            l = m;
        else
            r = m;
    }
    return l;
}

각 검사는 $O(n)$에 동작하고, 바깥쪽 이진 탐색은 $O(\log n)$번의 검사를 수행하므로 점근적 복잡도는 $O(n \log X)$가 됩니다.

#«프린터»

프린터가 두 대 있습니다. 한 대는 $x$분마다 한 장을, 다른 한 대는 $y$분마다 한 장을 인쇄합니다. 두 프린터가 $n$장을 인쇄하는 데 몇 분이 걸리겠습니까?

$n > 0$

여기서는 앞의 문제와 달리 공식을 이용한 직접적인 풀이가 있는 것으로 보입니다. 하지만 그것을 고민하는 대신 문제를 역문제로 간단히 환원할 수 있습니다. 분 수 $t$(답)가 주어졌을 때 그 시간 동안 몇 장이 인쇄되는지 어떻게 알 수 있을지 생각해 봅시다. 아주 쉽습니다: