연습 문제

탐색 문제의 핵심은 "무엇이 단조로운가"를 찾는 것입니다. 아래 다섯 문제는 경계 찾기, 직전 값 찾기, 답을 이분 탐색하기, 배열 모양에서 단조 조건 만들기를 차례로 연습합니다. 먼저 스스로 풀어 본 뒤 접근법과 풀이를 확인하세요.

문제 1. 점수 구간에 든 학생 수

오름차순으로 정렬된 시험 점수 목록 scores와 질의 여러 개가 주어집니다. 각 질의 (L, R)에 대해 점수가 L 이상 R 이하인 학생 수를 구하세요. 학생 수와 질의 수는 각각 최대 10만입니다.

접근: 질의마다 전체를 훑으면 최대 100억 번 비교가 필요합니다. R 이하인 개수는 upper_bound(R), L 미만인 개수는 lower_bound(L)이므로 그 차이가 답입니다. 질의 하나에 O(log n)입니다.

from bisect import bisect_left, bisect_right


def count_in_range(scores, queries):
    return [bisect_right(scores, r) - bisect_left(scores, l) for l, r in queries]


print(count_in_range([40, 55, 55, 70, 85, 90], [(50, 80), (55, 55), (91, 100)]))
# [3, 2, 0]

문제 2. 그 시각의 센서 값

센서가 기록한 (시각, 값) 목록이 시각 오름차순으로 주어집니다. 질의 시각 t마다 "t 이전 또는 t에 기록된 가장 최근 값"을 구하세요. 그런 기록이 없으면 None입니다.

접근: t보다 큰 첫 기록의 위치가 upper_bound(t)이므로 그 바로 앞이 답입니다. 위치가 0이면 앞선 기록이 없습니다. 시각만 따로 모은 목록을 한 번 만들어 두면 질의마다 이진 탐색 한 번이면 됩니다.

from bisect import bisect_right


def value_at(log, t):
    times = [time for time, _ in log]
    i = bisect_right(times, t) - 1
    return log[i][1] if i >= 0 else None


log = [(100, 21.5), (160, 22.0), (220, 21.8)]
print(value_at(log, 99), value_at(log, 160), value_at(log, 500))
# None 22.0 21.8

실제로 질의가 많다면 times를 함수 밖에서 한 번만 만들어 재사용합니다.

문제 3. 책을 k권으로 묶기

장(章)마다 쪽수가 담긴 목록 pages가 있습니다. 순서를 바꾸지 않고 연속된 장끼리 묶어 최대 k권으로 제본하려고 합니다. 가장 두꺼운 권의 쪽수를 최소로 만들 때 그 값을 구하세요.

접근: "가장 두꺼운 권을 cap 쪽 이하로 만들 수 있는가"는 cap이 커질수록 거짓에서 참으로 한 번만 바뀝니다. 가능 여부는 앞에서부터 cap을 넘기 직전까지 담는 탐욕 방식으로 O(n)에 판단합니다. 답의 범위는 가장 긴 장의 쪽수부터 전체 쪽수까지입니다. 전체 시간은 O(n log(합계))입니다.

def min_thickest(pages, k):
    def fits(cap):
        volumes, current = 1, 0
        for p in pages:
            if current + p > cap:
                volumes += 1
                current = 0
            current += p
        return volumes <= k

    lo, hi = max(pages), sum(pages)
    while lo < hi:
        mid = (lo + hi) // 2
        if fits(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


print(min_thickest([30, 10, 40, 20, 50], 2))   # 80
print(min_thickest([30, 10, 40, 20, 50], 3))   # 60

lo를 max(pages)부터 시작하므로 한 장이 cap보다 큰 경우는 따로 처리하지 않아도 됩니다.

문제 4. 산 모양 배열의 꼭대기

배열 a는 엄격히 증가하다가 한 지점을 지나 엄격히 감소합니다(길이 3 이상). 꼭대기 인덱스를 O(log n)에 구하세요.

접근: 조건 a[i] > a[i + 1]은 꼭대기 앞에서는 거짓, 꼭대기부터는 참입니다. 따라서 i를 [0, n - 1)에서 이진 탐색해 처음 참이 되는 위치를 찾으면 그곳이 꼭대기입니다. 삼분 탐색 없이 이진 탐색만으로 단봉 배열의 최댓값을 찾는 방법입니다.

def peak_index(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[mid + 1]:
            hi = mid
        else:
            lo = mid + 1
    return lo


print(peak_index([1, 4, 9, 12, 7, 3]))   # 3

문제 5. 회전된 배열의 시작점

서로 다른 정수를 오름차순으로 정렬한 뒤 어떤 지점에서 잘라 앞뒤를 바꾼 배열이 있습니다. 예를 들어 [3, 5, 8, 1, 2]입니다. 원래 첫 원소, 즉 최솟값의 인덱스를 구하세요.

접근: 마지막 원소 a[-1]과 비교하면 회전점 앞의 원소는 모두 a[-1]보다 크고, 회전점부터는 모두 a[-1] 이하입니다. 조건 a[i] <= a[-1]의 첫 참이 답입니다. 회전하지 않은 배열이면 0이 나옵니다.

def rotation_start(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= a[-1]:
            hi = mid
        else:
            lo = mid + 1
    return lo


print(rotation_start([3, 5, 8, 1, 2]), rotation_start([1, 2, 3]))   # 3 0

정리

• 구간 개수와 직전 값 찾기는 bisect_left·bisect_right 두 함수로 해결됩니다.
• 최소·최대를 묻는 최적화 문제는 "이 값으로 가능한가"로 바꿔 답을 이분 탐색합니다.
• 정렬되지 않은 배열이라도 이웃 비교나 기준값 비교로 단조 조건을 만들면 이진 탐색을 쓸 수 있습니다.