이분 탐색 - 정렬된 곳과 답의 범위에서

이 장에서 배우는 것

앞 장에서 정렬은 자료의 순서를 만들어 비교를 쉽게 하는 방법이었다. 이번에는 그 순서를 이용해 살펴볼 범위를 줄인다. 정렬된 예약 번호에서 원하는 번호를 찾는 일과, 하루 처리 용량의 최솟값을 정하는 일은 겉으로 다른 문제다. 그러나 두 문제 모두 어느 지점에서 판단 결과가 한 번 바뀐다는 공통점이 있다.

이분 탐색(binary search)은 이 경계를 찾는 방법이다. 가운데를 확인한 뒤 답이 있을 수 없는 쪽을 버린다. 중요한 것은 가운데 인덱스를 계산하는 식보다, 버린 구간에 무엇이 들어 있는지 설명하는 일이다. 그 설명을 불변식으로 고정하면 중복값과 빈 리스트, 마지막 원소 뒤의 경계까지 같은 코드로 처리할 수 있다.

• 이상인 첫 위치와 초과인 첫 위치를 구분하고, 두 경계로 중복값의 개수를 구한다.
• 반열린 구간과 불변식으로 탐색 범위를 관리해 인덱스가 하나 어긋나는 실수를 줄인다.
• 표준 라이브러리 bisect 모듈을 상황에 맞게 사용한다.
• 가능 여부가 한 번만 바뀌는 조건에서 답을 이분 탐색하는 매개변수 탐색을 설계한다.
• 최소 용량을 구하는 빠른 풀이를 작은 입력의 느린 정답과 전수 대조한다.

문제 상황

공유 작업실에서 예약 번호를 정렬해 보관한다고 하자. 같은 번호는 함께 예약한 여러 좌석을 나타낸다. 오늘의 번호가 [12, 18, 18, 18, 27, 35]라면 번호 18이 있는지만 알아서는 부족하다. 해당 예약의 좌석을 한꺼번에 표시하려면 어디서 시작하고 어디서 끝나는지 알아야 한다.

왼쪽 경계는 18 이상인 첫 위치인 1이다. 오른쪽 경계는 18을 초과하는 첫 위치인 4다. 따라서 예약 18의 좌석은 인덱스 1, 2, 3에 있으며 개수는 4 − 1 = 3이다. 값이 없는 경우에도 두 경계를 찾는 규칙은 유지된다. 번호 20의 두 경계는 모두 4이므로 개수는 0이다.

또 다른 업무는 순서대로 도착한 전시 물품을 며칠에 나누어 운송하는 일이다. 각 물품의 무게는 양의 정수이며 물품 하나를 나누어 싣지 않는다. 도착 순서를 바꿀 수 없고, 하루에 운송하는 물품은 남은 물품의 앞부분부터 연속해서 고른다. 모든 물품을 정해진 일수 이내에 보내려면 하루 적재 용량을 최소 얼마로 정해야 하는지 구한다.

예를 들어 무게가 [4, 2, 7, 3, 5]이고 허용 일수가 3일이면 용량 8은 부족하다. [4, 2], [7], [3, 5]로 나누어 보낼 수 있으므로 충분해 보이지만, 이 경우는 정확히 3일이므로 실제로 충분하다. 용량 7에서는 [4, 2], [7], [3], [5]로 4일이 필요하다. 따라서 정답은 8이다. 이런 경계의 앞뒤를 직접 확인하는 습관이 문제 해석의 착오를 줄인다.

첫 문제는 정렬된 리스트의 위치를 찾는다. 둘째 문제는 정답 후보인 용량을 찾는다. 탐색 대상은 달라도, 왼쪽에는 조건을 만족하지 않는 값이 있고 오른쪽에는 만족하는 값이 있도록 나누는 원리는 같다.

경계를 찾는 반열린 구간과 불변식

하한 경계(lower bound)는 정렬된 리스트에서 목표값 이상인 첫 위치다. 상한 경계(upper bound)는 목표값을 초과하는 첫 위치다. 여기서 반환값은 원소가 아니라 위치다. 길이가 n인 리스트의 경계는 0부터 n까지 가능하다. n은 마지막 원소 뒤의 위치이며 실제 원소의 인덱스가 아니다.

탐색할 원소의 범위는 [lo, hi)로 표시한다. lo는 포함하고 hi는 포함하지 않는 반열린 구간이다. 길이는 hi − lo이고, lo와 hi가 같으면 비어 있다. 처음에 lo = 0, hi = n으로 두면 리스트 전체가 된다. 빈 리스트도 별도 규칙 없이 [0, 0)에서 시작해 곧바로 끝난다.

하한 경계를 찾을 때는 다음 설명을 반복 내내 유지한다. lo보다 앞의 값은 모두 목표값보다 작다. hi부터 뒤의 값은 모두 목표값 이상이다. 그 사이 원소의 분류만 아직 끝나지 않았다. 실제 경계 위치는 lo 이상 hi 이하에 있다. 미분류 원소의 구간이 [lo, hi)라는 말과, 답의 위치가 [lo, hi]에 있다는 말은 구분해야 한다.

가운데 위치 mid = (lo + hi) // 2를 확인한다. 그 값이 목표값보다 작으면 mid까지는 경계가 될 수 없으므로 lo = mid + 1로 옮긴다. 그렇지 않으면 mid가 첫 경계일 가능성이 있으므로 hi = mid로 옮긴다. 두 경우 모두 이미 확정한 구간의 설명이 유지된다.

번호 목록 [12, 18, 18, 18, 27, 35]에서 18의 하한 경계를 손으로 따라가 보자. 표의 범위는 각 비교를 하기 직전의 상태다.

18 이상인 첫 위치를 찾는 과정

현재 범위	가운데 위치와 값	판단	다음 범위
[0, 6)	3, 값 18	18 이상이다	[0, 3)
[0, 3)	1, 값 18	18 이상이다	[0, 1)
[0, 1)	0, 값 12	18보다 작다	[1, 1)

마지막에는 lo = hi = 1이다. lo 앞은 모두 18보다 작고, lo부터는 모두 18 이상이므로 1이 찾던 경계다. 원소가 목표값과 같아도 즉시 반환하지 않는 이유가 여기에 있다. 같은 값이 왼쪽에 더 있을 수 있기 때문이다.

상한 경계에서는 확정 구간의 설명만 바꾼다. lo 앞은 모두 목표값 이하이고, hi부터는 모두 목표값 초과다. 따라서 가운데 값이 목표값 이하일 때 lo = mid + 1로 옮긴다. 하한 경계 코드의 비교 연산자 하나가 달라지지만, 그 차이는 어느 쪽에 같은 값을 포함할지 결정한다.

종료도 확인할 수 있다. lo < hi일 때 mid는 lo 이상 hi 미만이다. lo를 mid + 1로 바꾸거나 hi를 mid로 바꾸면 구간 길이가 반드시 줄어든다. 길이는 음수가 될 수 없으므로 반복은 끝난다. 불변식의 유지와 종료 시 상태를 합치면 반환 위치가 올바르다는 근거가 된다.

한 번 비교할 때 남은 구간은 대략 절반이 된다. 길이가 n일 때 시간 복잡도는 O(log(n + 1))이고 추가 공간은 O(1)이다. n + 1로 쓰면 빈 리스트까지 같은 표현에 포함할 수 있다. 이미 정렬된 자료를 가정한 비용이며, 먼저 정렬해야 한다면 정렬 비용을 별도로 더한다.

bisect로 경계를 활용하기

Python의 bisect 모듈은 같은 경계 연산을 제공한다. bisect_left는 하한 경계, bisect_right는 상한 경계에 해당한다. 두 함수 모두 정렬 상태를 전제로 한다. 함수가 정렬 여부를 대신 검사하거나 자료를 정렬해 주지는 않는다.

from bisect import bisect_left, bisect_right

numbers = [12, 18, 18, 18, 27, 35]
left = bisect_left(numbers, 18)
right = bisect_right(numbers, 18)

print(left, right, right - left)

이 조각의 출력은 1 4 3이다. 같은 번호의 위치는 [left, right)이며, 실제 리스트를 복사하지 않고도 개수를 right − left로 구할 수 있다. 원소가 있는지만 확인하려면 left가 리스트 길이보다 작은지 먼저 검사한 다음 해당 값이 목표값과 같은지 확인한다.

position = bisect_left(numbers, 40)
exists = position < len(numbers) and numbers[position] == 40

목표값이 모든 원소보다 크면 position은 len(numbers)가 된다. 이 위치는 유효한 반환값이지만 numbers[position]으로 읽을 수는 없다. 위 코드에서는 and의 왼쪽이 거짓이면 오른쪽을 평가하지 않으므로 리스트 밖을 읽지 않는다.

경계 두 개를 조합하면 값의 구간도 셀 수 있다. a 이상 b 이하인 값의 개수는 a ≤ b일 때 bisect_right(numbers, b) − bisect_left(numbers, a)다. 왼쪽에서는 a를 포함하고 오른쪽에서는 b까지 포함해야 하므로 서로 다른 경계를 사용한다.

탐색이 빠르다는 사실과 리스트에 원소를 끼워 넣는 일이 빠르다는 사실은 다르다. 삽입 위치를 구하는 데에는 로그 시간이 들지만, 리스트 중간에 넣으면 뒤의 원소를 옮기는 비용이 생긴다. 이번 장에서는 정렬된 자료를 유지하는 전체 작업과 경계 조회 한 번의 비용을 구분한다.

완성 코드에는 경계 함수를 직접 작성하고 bisect의 결과와 대조하는 검사를 넣는다. 직접 구현은 불변식을 확인하는 데 쓰고, 실제 코드에서 단순한 경계 조회가 필요할 때는 표준 함수를 활용할 수 있다. 함수의 동작 정의는 Python bisect 공식 문서에서도 확인할 수 있다.

가능 여부를 이용해 최소 용량 찾기

매개변수 탐색(parametric search)은 정답 후보를 하나 정한 뒤 그 후보로 조건을 만족할 수 있는지 판단하는 방식이다. 여기서는 용량 C가 후보이고, “C로 모든 물품을 D일 이내에 보낼 수 있는가”가 판단 질문이다. 정답을 바로 계산하기 어려워도 특정 용량이 충분한지는 순서대로 적재해 보면 알 수 있다.

가능 여부를 검사할 때는 첫날부터 시작한다. 다음 물품을 실어도 용량을 넘지 않으면 같은 날에 싣는다. 넘으면 새 날을 시작한다. 물품 하나가 용량보다 크면 어느 날에도 실을 수 없으므로 곧바로 불가능이다. 이 검사는 무게 목록을 한 번 훑는다.

가능한 날에는 최대한 싣는 방식이 필요한 일수를 최소로 만드는 이유도 확인해야 한다. 첫날 실을 수 있는 가장 긴 앞부분을 고르면, 다른 유효한 계획이 첫날까지 보낸 위치보다 뒤처지지 않는다. 다음 날에도 같은 논리를 적용할 수 있다. 다른 계획이 하루에 보낼 수 있는 끝 위치까지 아직 도달하지 못했다면, 그 사이 남은 물품의 무게는 그 계획의 하루 적재량 이하이므로 현재 방식도 그 위치까지 보낼 수 있다. 따라서 매일 끝날 때 현재 방식은 다른 계획보다 뒤처지지 않는다.

이 논리를 날짜마다 이어 가면, 이 방식이 D일 안에 끝내지 못하는 경우 다른 유효한 계획도 D일 안에 끝내지 못한다. 단지 한 가지 적재 방법이 실패했다는 이유로 불가능을 선언하는 것이 아니라, 그 방법이 가장 적은 일수를 쓴다는 근거를 먼저 세운 것이다.

다음으로 판단 결과의 단조성을 확인한다. 어떤 용량에서 가능한 적재 계획은 더 큰 용량에서도 그대로 사용할 수 있다. 따라서 후보 용량을 작은 순서로 나열하면 불가능이 이어지다가 가능으로 한 번 바뀐다. 다시 불가능으로 돌아가지 않는다. 이 성질이 있어야 가운데 결과로 한쪽 전체를 버릴 수 있다.

탐색의 시작점은 가장 무거운 물품의 무게다. 이보다 작은 용량은 물품 하나도 처리하지 못할 수 있다. 끝점은 전체 무게의 합이다. 합만큼의 용량이면 첫날에 모두 실을 수 있으므로, D가 1 이상이라는 조건에서 항상 가능하다. 물품이 한 개 이상이고 모든 무게가 양의 정수라는 입력 조건도 이 설명에 포함된다.

여기서는 lo = max(weights), hi = sum(weights)로 시작한다. 미분류 후보는 [lo, hi)이며 hi는 가능하다고 알고 있는 후보다. lo보다 작은 후보는 불가능하고 hi 이상의 후보는 가능하다는 불변식을 유지한다. mid가 가능하면 hi = mid, 불가능하면 lo = mid + 1이다. 경계 탐색과 같은 모양이며, 리스트 조회를 가능 여부 검사로 바꾼 셈이다.

무게 [4, 2, 7, 3, 5]를 3일 이내에 보내는 용량 탐색

lo, hi	시험 용량	필요 일수	범위 갱신
7, 21	14	2일	hi = 14
7, 14	10	3일	hi = 10
7, 10	8	3일	hi = 8
7, 8	7	4일	lo = 8

물품 수를 n, 전체 무게를 S, 가장 큰 무게를 M이라 하자. 가능 여부 검사는 O(n)이고, 용량 탐색의 반복 횟수는 O(log(S − M + 2))이다. 따라서 전체 시간은 O(n log(S − M + 2)), 입력을 제외한 추가 공간은 O(1)이다. 정수 연산 하나의 비용을 일정하게 보는 코딩 테스트의 일반적인 계산 기준이다.

대조할 느린 풀이는 모든 날짜 경계를 열거한다. n개 물품 사이에는 n − 1개의 틈이 있다. 각 틈에서 날짜를 나눌지 말지를 모두 선택하고, 만들어진 구간 수가 D 이하인 경우만 살핀다. 그 계획에 필요한 용량은 구간별 무게 합의 최댓값이다. 모든 계획에서 이 값의 최솟값을 고르면 정답이다.

틈마다 선택이 두 개이므로 계획은 2의 n − 1제곱 개다. 각 계획을 O(n)에 계산하면 시간은 O(n × 2의 n − 1제곱), 추가 공간은 O(n)이다. 작은 입력 검사용으로는 충분하다. 빠른 풀이의 가능 여부 함수를 재사용하지 않으므로, 그 함수의 오류까지 함께 놓칠 가능성을 줄인다.

완성 코드

다음 프로그램을 main.py로 저장한다. 예시 입력은 문자열을 io.StringIO로 감싸 코딩 테스트의 줄 단위 입력을 흉내 낸다. 외부 입력을 기다리지 않으며, 경계 검사와 최소 용량 검사를 마친 뒤 종료한다. 난수를 사용하지 않아 실행 결과는 일정하다.

import io
from bisect import bisect_left, bisect_right
from itertools import product


def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def can_ship(weights, days, capacity):
    used_days = 1
    load = 0
    for weight in weights:
        if weight > capacity:
            return False
        if load + weight > capacity:
            used_days += 1
            load = 0
        load += weight
        if used_days > days:
            return False
    return True


def minimum_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(weights, days, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def brute_capacity(weights, days):
    n = len(weights)
    best = sum(weights)

    for cuts in product((False, True), repeat=n - 1):
        groups = 1
        load = weights[0]
        largest = 0

        for index, cut in enumerate(cuts, start=1):
            if cut:
                largest = max(largest, load)
                groups += 1
                load = 0
            load += weights[index]

        largest = max(largest, load)
        if groups <= days:
            best = min(best, largest)

    return best


def check_boundaries():
    checked = 0
    for length in range(5):
        for values in product(range(3), repeat=length):
            if list(values) != sorted(values):
                continue
            for target in range(-1, 4):
                left = lower_bound(values, target)
                right = upper_bound(values, target)

                slow_left = sum(value < target for value in values)
                slow_right = sum(value <= target for value in values)

                if (left, right) != (slow_left, slow_right):
                    raise AssertionError((values, target, left, right))
                if left != bisect_left(values, target):
                    raise AssertionError("bisect_left mismatch")
                if right != bisect_right(values, target):
                    raise AssertionError("bisect_right mismatch")
                checked += 1
    return checked


def check_capacities():
    checked = 0
    for length in range(1, 6):
        for weights in product(range(1, 4), repeat=length):
            for days in range(1, length + 1):
                fast = minimum_capacity(weights, days)
                slow = brute_capacity(weights, days)
                if fast != slow:
                    raise AssertionError((weights, days, fast, slow))
                checked += 1
    return checked


def main():
    source = io.StringIO("5 3\n4 2 7 3 5\n")
    n, days = map(int, source.readline().split())
    weights = list(map(int, source.readline().split()))

    if n < 1 or len(weights) != n:
        raise ValueError("invalid item count")
    if days < 1 or any(weight <= 0 for weight in weights):
        raise ValueError("invalid days or weights")

    numbers = [12, 18, 18, 18, 27, 35]
    left = bisect_left(numbers, 18)
    right = bisect_right(numbers, 18)

    print(f"예약 18: 왼쪽={left}, 오른쪽={right}, 개수={right - left}")
    print(f"최소 용량: {minimum_capacity(weights, days)}")
    print(f"완전 탐색 용량: {brute_capacity(weights, days)}")
    print(f"경계 전수 대조: {check_boundaries()}건 통과")
    print(f"용량 전수 대조: {check_capacities()}건 통과")


if __name__ == "__main__":
    main()

줄별 해설

가져오기 구문. io는 문자열 입력을 파일처럼 읽는 데 사용한다. bisect의 두 함수는 예약 번호 조회와 직접 구현의 대조에 사용한다. product는 정해진 후보들에서 가능한 조합을 빠짐없이 만든다. 모두 표준 라이브러리에 포함되어 있다.

lower_bound의 초기화. lo, hi = 0, len(values)는 미분류 원소 전체를 지정한다. while lo < hi는 원소가 하나라도 남았을 때만 비교한다. 이 조건 때문에 values[mid]를 읽을 때 mid는 항상 실제 인덱스 범위 안에 있다.

두 경계 함수의 분기. lower_bound에서는 values[mid] < target이면 왼쪽을 버린다. upper_bound에서는 values[mid] <= target이면 왼쪽을 버린다. 같음을 왼쪽 확정 구간에 포함하는지에 따라 첫 동일값 앞과 마지막 동일값 뒤가 갈린다.

can_ship의 상태. used_days는 현재 사용하는 날까지 포함한 일수이고 load는 그날의 적재량이다. 물품이 존재한다는 조건에서 첫날부터 시작하므로 used_days = 1이다. 새 날로 넘어갈 때 load를 0으로 만든 뒤 현재 물품을 더한다. 해당 물품을 빠뜨리거나 두 번 더하지 않도록 load += weight를 분기 밖에 한 번만 둔다.

용량 초과와 일수 초과 검사. weight > capacity는 쪼갤 수 없는 물품을 처리하지 못하는 경우다. load + weight > capacity는 현재 날짜를 마감해야 하는 경우다. 적재량이 용량과 같으면 실을 수 있으므로 두 비교에 모두 엄격한 초과를 사용한다. 날짜가 제한을 넘는 순간에는 뒤를 더 보아도 가능해지지 않으므로 즉시 거짓을 반환한다.

minimum_capacity의 반복. mid가 가능하면 mid보다 큰 후보를 살필 필요가 없다. 그러나 mid 자체가 최소일 수 있으므로 hi = mid로 남긴다. 불가능하면 mid까지 버려 lo = mid + 1로 옮긴다. lo와 hi가 만나면 그보다 작은 후보는 불가능하고 그 후보는 가능하므로 답이다.

brute_capacity의 날짜 경계. cuts의 각 참·거짓은 인접한 두 물품 사이에서 날짜를 나눌지 정한다. enumerate의 start=1은 첫 번째 틈이 인덱스 0과 1 사이임을 반영한다. 참이면 앞 구간의 무게를 largest에 반영하고 새 구간을 시작한다. 반복이 끝난 뒤 마지막 구간도 반드시 반영한다.

느린 풀이의 초기 정답. best = sum(weights)는 하루에 모두 보내는 유효한 계획이다. 각 계획의 구간 수가 days 이하일 때만 best를 줄인다. 허용 일수를 모두 채울 의무는 없으므로 groups == days가 아니라 groups <= days를 사용한다.

check_boundaries의 입력 범위. 길이 0부터 4까지, 값 0부터 2까지인 비내림차순 목록을 모두 검사한다. 목표값은 −1부터 3까지여서 자료의 양 끝 밖에 있는 경우도 포함한다. 느린 정답은 목표보다 작은 원소 수와 목표 이하인 원소 수다. 정렬된 목록에서는 이 수가 각각 경계 위치와 같다.

check_capacities의 대조. 물품 수 1부터 5까지, 각 무게 1부터 3까지, 허용 일수 1부터 물품 수까지를 모두 조합한다. 각 입력에서 빠른 탐색과 모든 날짜 분할의 결과가 같은지 확인한다. D가 물품 수 이상이면 물품마다 하루씩 배정할 수 있어 답이 최대 무게로 같아지므로, 전수 범위에서는 대표인 D = n까지 검사한다.

main의 입력과 출력. 첫 줄은 물품 수와 허용 일수, 둘째 줄은 무게 목록이다. 개수와 양수 조건을 확인한 뒤 문제 풀이와 검사를 호출한다. 마지막 조건문은 파일을 직접 실행했을 때 main을 호출한다. 검사에서 차이가 발견되면 성공 문구 대신 예외가 발생한다.

실행 결과

다음 명령으로 실행한다.

python3 main.py

예상 출력은 다음과 같다.

예약 18: 왼쪽=1, 오른쪽=4, 개수=3
최소 용량: 8
완전 탐색 용량: 8
경계 전수 대조: 175건 통과
용량 전수 대조: 1641건 통과

경계 검사에서 정렬된 목록은 길이별로 1, 3, 6, 10, 15개다. 합계 35개에 목표값 5개를 적용해 175건이 된다. 용량 검사는 길이 n마다 무게 목록이 3의 n제곱 개이고 허용 일수가 n가지다. 따라서 3 + 18 + 81 + 324 + 1215 = 1641건이다.

전수 대조는 지정한 작은 범위에서 오류가 없음을 확인한다. 모든 크기에 대한 정확성은 불변식과 가능 여부 검사의 근거가 담당한다. 둘은 서로 다른 역할을 한다. 설명은 맞아 보여도 구현에서 등호를 잘못 쓸 수 있고, 작은 검사에 통과해도 정렬 전제나 단조성이 빠진 설계는 다른 입력에서 실패할 수 있다.

실무에서 자주 틀리는 것

반열린 구간에 닫힌 구간 갱신을 섞는다

다음은 하한 경계를 찾는 반열린 구간에 hi = mid − 1을 섞은 잘못된 부분이다. mid가 답일 가능성까지 버린다. 예를 들어 [1, 3]에서 목표값 2를 찾으면 경계 1을 남기지 못한다.

if values[mid] < target:
    lo = mid + 1
else:
    hi = mid - 1

반열린 구간에서는 다음처럼 고친다. 반복 조건, 초기 끝점, 갱신 규칙을 하나의 묶음으로 사용해야 한다.

if values[mid] < target:
    lo = mid + 1
else:
    hi = mid

반환 위치를 확인하지 않고 읽는다

아래 코드는 목표값이 모든 원소보다 클 때 리스트 밖을 읽는다. 빈 리스트에서도 같은 문제가 생긴다.

position = bisect_left(values, target)
exists = values[position] == target

반환 위치가 길이와 같을 수 있음을 반영한다. 길이 검사부터 평가하도록 순서를 지킨다.

position = bisect_left(values, target)
exists = position < len(values) and values[position] == target

목표 일수와 정확히 같아야 가능하다고 판단한다

용량이 넉넉해져 필요한 일수가 줄었는데 다음처럼 판단하면 거짓이 된다. 이 문제는 정해진 일수 이내에 끝내는 조건이므로, 이 판단은 문제의 뜻과 다르다.

return used_days == days

일수를 덜 써도 가능한 것으로 처리한다. 완성 코드처럼 제한을 넘을 때 조기에 반환해도 되고, 끝까지 계산한 뒤 다음 조건으로 판단해도 된다.

return used_days <= days

가능한 가운데 후보를 함께 버린다

다음 코드는 mid가 최소 용량일 수 있는데도 후보에서 제외한다. 더구나 hi는 가능한 후보라는 불변식도 유지하지 못할 수 있다.

if can_ship(weights, days, mid):
    hi = mid - 1
else:
    lo = mid + 1

첫 가능한 값을 찾는 탐색에서는 가능한 mid를 오른쪽 끝점으로 남긴다. 반대로 불가능한 mid는 답이 아니므로 버린다.

if can_ship(weights, days, mid):
    hi = mid
else:
    lo = mid + 1

한눈에 보기

경계 탐색과 최소 용량 탐색의 대응

항목	하한 경계	상한 경계	최소 용량
찾는 첫 참	값 ≥ 목표	값 > 목표	D일 이내 가능
lo 앞의 상태	목표보다 작음	목표 이하	불가능
hi부터의 상태	목표 이상	목표 초과	가능
가운데가 참	hi = mid	hi = mid	hi = mid
가운데가 거짓	lo = mid + 1	lo = mid + 1	lo = mid + 1
한 번의 판단	O(1)	O(1)	O(n)

이분 탐색을 쓰기 전에는 세 문장을 적어 보면 좋다. 무엇이 거짓에서 참으로 바뀌는지, 시작 범위가 답을 포함하는지, 가운데 후보를 어느 경우에 남기는지다. 정렬된 자료에서는 비교 결과가 그 순서를 만들고, 용량 문제에서는 가능 여부의 단조성이 그 순서를 만든다.

연습 문제

1. 정렬된 예약 번호가 [6, 9, 9, 14, 20, 20]이다. 목표값 9와 11에 대해 하한 경계, 상한 경계, 같은 값의 개수를 각각 구한다. 목표값 25의 하한 경계도 구한다.
2. 정렬된 재고 수량이 [2, 4, 4, 7, 10, 13]이다. 4 이상 10 이하인 수량의 개수를 bisect 함수 두 번으로 구하는 코드를 쓴다. 오른쪽 경계에 bisect_left를 쓰면 어떤 값이 빠지는지 설명한다.
3. 운송할 물품의 무게가 [3, 6, 2, 4]이고 허용 일수가 2일이다. 최소 용량을 구한다. 그 용량의 적재 계획과 바로 작은 용량이 불가능한 이유를 함께 적는다.
4. minimum_capacity의 반복에서 lo = mid + 1을 lo = mid로 바꾸었다. 무게 [2, 3], 허용 일수 1일일 때 어떤 상태에서 반복이 끝나지 않는지 설명한다.

정답과 해설

1. 목표값 9의 하한 경계는 1, 상한 경계는 3, 개수는 2다. 목표값 11의 두 경계는 모두 3이고 개수는 0이다. 목표값 25의 하한 경계는 리스트 길이인 6이다. 반환 위치가 6이라는 것은 조건을 만족하는 실제 원소가 없다는 뜻이다.

2. 다음과 같이 계산하면 4가 나온다. 오른쪽에 bisect_left를 사용하면 10의 앞에서 구간을 끝내므로 10이 빠지고 결과가 3이 된다.

   stocks = [2, 4, 4, 7, 10, 13]
   count = bisect_right(stocks, 10) - bisect_left(stocks, 4)

3. 최소 용량은 9다. 첫날 [3, 6], 둘째 날 [2, 4]로 나누면 된다. 용량 8에서는 첫날 3 다음에 6을 더 실을 수 없다. 둘째 날에는 6과 2를 싣지만 4가 남아 셋째 날이 필요하다. 날짜를 나누는 위치를 모두 보아도 [3] 뒤에서 나누면 남은 합이 12, [3, 6] 뒤에서 나누면 앞의 합이 9, [3, 6, 2] 뒤에서 나누면 앞의 합이 11이다. 따라서 용량 8 이하로 2일에 끝낼 수 없다.

4. 처음 범위는 lo = 3, hi = 5다. mid = 4는 불가능하므로 잘못된 갱신 뒤 lo = 4, hi = 5가 된다. 다음 mid도 4이며 불가능하다. lo = mid는 lo를 그대로 두므로 같은 상태가 반복된다. 불가능한 후보를 제외하는 mid + 1이 구간 길이를 줄이는 역할도 한다.