D-3: 이진 탐색·매개변수 탐색 — 정렬된 공간을 절반씩, 답 자체를 이분한다

안녕하세요, 홍순구 튜터입니다. 지난 시간까지 우리는 데이터를 줄 세우는 정렬을 손으로 짰습니다. 그리고 정렬은 그 자체가 목적이 아니라 '다음 알고리즘의 발판'이라고 여러 번 말했죠. 오늘 드디어 그 발판 위에 첫 무기를 올립니다. 정렬된 배열에서 원하는 값을 눈 깜짝할 사이에 찾는 이진 탐색이에요.

먼저 감을 잡아 봅시다. 700쪽짜리 전화번호부에서 '홍순구'를 찾는다고 해 봐요. 첫 장부터 한 장씩 넘기면 운이 나쁠 때 700번을 넘겨야 합니다. 하지만 우리는 그렇게 안 하죠. 중간쯤 펼쳐 보고 '홍'이 뒤에 있으면 앞쪽 절반을 통째로 덮어 버립니다. 한 번 펼칠 때마다 볼 곳이 반으로 줄어요. 이게 오늘의 주인공, 이진 탐색입니다.

여기서 한 걸음 더 나아가면 오늘의 진짜 반전이 나옵니다. "가장 길게 자르면 몇 미터일까?" 같은, 배열에서 값을 찾는 것과는 전혀 달라 보이는 문제도 사실은 '답 자체를 절반씩 좁혀' 풀 수 있어요. 최적화 문제를 예/아니오 결정 문제로 바꾸는 매개변수 탐색까지, 오늘 함께 가 봅니다.

 오늘의 여정 — 이진 탐색, 절반씩 버리는 힘

   ① 절반씩 버린다     정렬된 배열에서 O(log n)에 찾기 (전화번호부 넘기듯)
   ② 경계를 찾는다     lower/upper bound · 내장 bisect (값이 아니라 경계)
   ③ 답을 이분한다     매개변수 탐색 — 최적화 문제를 결정 문제로

💡 오늘 수업의 핵심 — "정렬된 배열을 절반씩 좁혀 O(log n)에 찾고, 나아가 '답 자체를 이분'하는 매개변수 탐색으로 최적화 문제를 결정 문제로 바꾼다"

🎯 학습 목표

• 이진 탐색으로 정렬된 배열을 O(log n)에 탐색하고, 경계(off-by-one)를 정확히 처리한다.
• lower/upper bound로 값의 경계를 찾고, 내장 bisect를 실전에서 언제 쓸지 판단한다.
• 매개변수 탐색으로 최적화 문제를 예/아니오 결정 문제로 바꿔 답을 이분한다.

Step 1: "절반씩 버린다 — 왜 이진 탐색인가"

지난 시간까지의 정렬은 전부 데이터를 '먼저 줄 세우는' 준비였습니다. 오늘부터는 그 줄 세운 배열을 '빠르게 쓰는' 쪽으로 넘어옵니다. 그 첫 번째가 탐색이에요.

정렬된 배열 [1, 3, 5, 7, 9, 11]에서 9를 찾는다고 해 봅시다. 가장 단순한 방법은 앞에서부터 하나씩 견주는 겁니다. 이걸 선형 탐색(linear search)이라 하고, 최악의 경우 원소 n개를 전부 봐야 하니 O(n)이에요. 배열이 커질수록 정직하게 느려집니다.

하지만 배열이 '정렬돼 있다'는 사실을 쓰면 이야기가 달라져요. 가운데 원소를 하나 찍어 찾는 값과 견주면, 한쪽 절반은 볼 필요조차 없어집니다. 찾는 값이 가운데보다 크면 왼쪽 절반은 통째로 버리고, 작으면 오른쪽을 버려요. 한 번 비교에 후보가 반으로 줄어드니, n개를 훑어도 약 log₂n번이면 끝납니다.

 선형 탐색 — 앞에서부터 하나씩          이진 탐색 — 가운데를 찍어 절반을 버린다

   n = 16   → 최악 16번                  n = 16   → 최악 4번   (16→8→4→2→1)
   n = 10억 → 최악 10억 번               n = 10억 → 최악 30번  (log₂10억 ≈ 30)

이 차이를 이 과목의 잣대 '1초 ≈ 1억 연산'으로 재 봅시다. n이 10억일 때 선형 탐색은 약 10억 번, 즉 10초 넘게 걸려 시간 초과예요. 그런데 이진 탐색은 고작 30번입니다. 눈 깜짝할 사이죠. 정렬만 돼 있다면, 탐색은 사실상 공짜에 가까워집니다.

핵심 전제는 딱 하나예요. '정렬돼 있어야 한다'는 것. 뒤죽박죽인 배열에선 가운데를 찍어도 어느 절반을 버릴지 근거가 없으니까요. 그래서 이진 탐색은 늘 정렬된 배열을 발판으로 깔고 시작합니다. 지난 시간에 "정렬해 두면 뭐가 좋은가"의 답이 바로 이겁니다.

🎯 코테에서는 "정렬한 뒤 이진 탐색"이 하나의 세트로 자주 나옵니다. 입력이 정렬돼 있거나, 정렬해도 되는 데이터라면 '어떤 값이 있는지', '조건을 만족하는 첫 위치가 어디인지'를 O(log n)에 물을 수 있어요. n이 수십만~수억으로 크면서 "빠르게 찾아라"가 보이면 이진 탐색을 먼저 의심해 봅니다.

💡 한 줄 정리

이진 탐색은 정렬된 배열에서 가운데를 찍어 절반을 버려 O(log n)에 찾으며, 그 전제는 '배열이 정렬돼 있어야 한다'는 것이다.

Step 2: "직접 짜 보는 이진 탐색 — 경계와의 싸움"

원리를 봤으니 손으로 짜 봅시다. 이진 탐색의 뼈대는 '아직 후보인 구간'을 두 변수 lo, hi로 잡고, 가운데 mid를 찾는 값과 견줘 그 구간을 좁혀 가는 겁니다.

# algorithms/binary_search.py
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

한 줄씩 뜯어봅시다. lo와 hi는 후보 구간의 양 끝 index예요. 처음엔 배열 전체라 0과 len(arr) - 1입니다. 가운데 mid를 찾은 뒤 세 갈래로 나뉘어요. arr[mid]가 찾는 값과 같으면 바로 그 index를 돌려주고, 찾는 값보다 작으면 target은 오른쪽에 있으니 lo를 mid + 1로 당깁니다. 크면 반대로 hi를 mid - 1로 줄여요.

이 +1, -1이 이진 탐색에서 가장 많이 틀리는 곳, 이른바 off-by-one(경계 하나 차이)입니다. mid는 방금 이미 확인했으니 다음 후보에서 빼야 해요. 그래서 버릴 때 mid 자신을 다시 넣지 않으려고 +1, -1을 붙입니다. 구간을 닫힌 구간 [lo, hi]로 잡았으니 반복 조건도 lo <= hi(양 끝이 같아도 아직 후보 하나가 남음)가 됩니다. 구간이 완전히 비면(lo > hi) 없는 값이라 -1을 돌려줘요.

실제로 도는 과정을 눈으로 따라가 봅시다.

 binary_search([1, 3, 5, 7, 9, 11], 9)   — 닫힌 구간 [lo, hi]를 좁힌다

   index:   0   1   2   3   4   5
   arr:     1   3   5   7   9  11

   ① lo=0, hi=5 → mid=2, arr[2]=5  < 9  → lo = mid+1 = 3   (index 0~2 버림)
   ② lo=3, hi=5 → mid=4, arr[4]=9  == 9 → 찾았다! index 4 반환

여섯 개짜리 배열을 단 두 번의 비교로 끝냈어요. 실제로 binary_search([1, 3, 5, 7, 9, 11], 7)은 3을, 없는 값인 binary_search([1, 3, 5, 7, 9, 11], 6)은 -1을 돌려줍니다. 시간 복잡도는 후보가 매번 절반이 되니 O(log n), 추가로 쓰는 공간은 변수 몇 개뿐이라 O(1)이에요.

🎯 코테에서는 이 열두 줄이 손에 붙어 있어야 합니다. 경계 조건(<=인지 <인지, mid를 버릴 때 ±1을 붙이는지)에서 한 끗을 틀리면 무한 루프에 빠지거나 답이 하나씩 어긋나요. 그래서 아예 '내 손에 맞는 한 가지 틀'을 정해 두고 늘 똑같이 쓰는 걸 추천합니다.

💡 한 줄 정리

이진 탐색은 닫힌 구간 [lo, hi]를 while lo <= hi로 좁히며, mid를 버릴 때 ±1을 붙이는 경계 처리(off-by-one)가 정확성의 핵심이다.

Step 3: "값이 아니라 경계를 찾는다 — lower/upper bound"

방금 만든 binary_search에는 빈틈이 하나 있어요. 같은 값이 여러 개면 어떻게 될까요? [1, 2, 2, 2, 5, 7]에서 2를 찾으면, 세 개의 2 중 '어느 것'의 index가 나올지 알 수 없습니다. 가운데를 어떻게 찍느냐에 따라 1일 수도, 3일 수도 있어요.

그런데 실전에서는 "2가 있냐"보다 "2가 처음 나오는 위치가 어디냐", "2가 몇 개냐" 같은 질문이 훨씬 자주 나옵니다. 그래서 값을 찾는 대신 '경계'를 찾는 이진 탐색을 따로 익힙니다. 두 가지예요.

• lower bound: target '이상'이 처음 나오는 위치
• upper bound: target '초과'가 처음 나오는 위치

# algorithms/binary_search.py
def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Step 2와 달라진 곳을 짚어 봅시다. hi가 len(arr) - 1이 아니라 len(arr)에서 시작하고(찾는 값이 배열 맨 끝보다 커서 '끝에 끼워 넣을 위치'가 답일 수 있으니까요), 조건도 lo < hi인 반열린 구간 [lo, hi)입니다. arr[mid]가 target보다 작으면 mid는 절대 답이 될 수 없으니 버리고(lo = mid + 1), target 이상이면 mid도 후보라서 hi = mid로 남겨 둬요. 이렇게 좁히면 '이상이 처음인 위치'로 정확히 수렴합니다.

upper bound는 부등호 딱 하나만 다릅니다.

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

arr[mid] < target이 arr[mid] <= target으로 바뀌었죠. target과 '같은' 값까지 버리니, 같은 값들의 오른쪽 끝 다음으로 수렴해요. 이 둘을 그림으로 보면 한눈에 들어옵니다.

 arr = [1, 2, 2, 2, 5, 7]        target = 2
   index:  0   1   2   3   4   5
   값:     1   2   2   2   5   7
              └─── 2 ───┘

   lower_bound(2) = 1   ← 2 이상이 처음 나오는 위치 (첫 2의 index)
   upper_bound(2) = 4   ← 2 초과가 처음 나오는 위치 (index 4, 값 5)
   개수 = upper - lower = 4 - 1 = 3

경계 둘을 빼면 그 폭이 곧 '값의 개수'가 됩니다. 코드베이스에도 이 조합을 담아 뒀어요.

def count_occurrences(arr, target):
    return upper_bound(arr, target) - lower_bound(arr, target)

[1, 2, 2, 2, 5, 7]에서 count_occurrences(arr, 2)는 3을 돌려줍니다. 하나하나 세면 O(n)이지만, 경계 두 번이면 O(log n)이에요. 없는 값 6은 lower와 upper가 똑같이 5(끼워 넣을 위치)로 나와 개수 0이 됩니다.

🎯 코테에서는 "정렬된 수열에서 특정 값이 몇 개인가", "x 이상 y 이하가 몇 개인가" 같은 문제가 lower/upper bound의 단골입니다. 정렬 배열에서 범위를 세는 질문이 보이면, 하나씩 세지 말고 경계 두 번을 떠올리세요. 오늘 과제에서 직접 풀어 봅니다.

💡 한 줄 정리

lower bound는 target 이상이 처음인 위치, upper bound는 초과가 처음인 위치를 O(log n)에 찾으며, 부등호 하나(< vs <=) 차이로 갈리고 두 경계의 폭이 곧 값의 개수다.

Step 4: "실전은 bisect — 직접 구현 vs 내장"

여기까지 lower/upper bound를 손으로 짜 봤습니다. 이제 좋은 소식이에요. 파이썬은 이 경계 탐색을 표준 라이브러리 bisect로 이미 제공합니다. C-2에서 힙을 직접 짠 뒤 heapq를 썼던 것과 똑같은 흐름이에요. 원리를 손으로 봤으니, 실전에선 검증된 내장을 씁니다.

import bisect

arr = [1, 2, 2, 2, 5, 7]
bisect.bisect_left(arr, 2)     # → 1  (우리가 만든 lower_bound과 같다)
bisect.bisect_right(arr, 2)    # → 4  (upper_bound과 같다)

bisect.insort(arr, 4)          # arr가 [1, 2, 2, 2, 4, 5, 7]로 — 정렬을 유지하며 삽입

이름만 다를 뿐 동작이 똑같아요. bisect_left가 lower bound, bisect_right가 upper bound입니다. insort는 정렬을 유지한 채 값을 끼워 넣는데, 넣을 위치는 이진 탐색으로 O(log n)에 찾지만 실제로 배열 중간에 밀어 넣는 건 O(n)이 든다는 점만 기억하세요. 코드베이스 binary_search.py 아래에도 이 대조를 메모로 적어 뒀습니다.

# algorithms/binary_search.py (파일 끝, 실전 대조 메모)
#   bisect.bisect_left(arr, x)   ==  lower_bound(arr, x)
#   bisect.bisect_right(arr, x)  ==  upper_bound(arr, x)
#   bisect.insort(arr, x)        →  정렬을 유지하며 삽입(삽입 자체는 O(n))

그럼 언제 직접 짜고 언제 bisect를 쓸까요? 기준은 명확합니다.

🎯 코테에서는 정렬 배열의 경계 탐색은 bisect 두 줄이면 끝납니다. 하지만 곧 배울 매개변수 탐색처럼 '판정 조건이 배열이 아닌 곳'에 있으면 bisect로는 안 되고 직접 짜야 해요. 그래서 원리를 손에 쥔 사람만 라이브러리를 언제 믿고 언제 직접 짤지 판단할 수 있습니다.

💡 한 줄 정리

bisect_left는 lower bound, bisect_right는 upper bound와 같아 실전 경계 탐색은 bisect로 끝나지만, 표준에 없는 변형은 직접 짜야 하므로 원리를 쥐고 있어야 한다.

i = bisect.bisect_left(arr, x)          # x가 들어갈 위치
exists = i < len(arr) and arr[i] == x   # 그 위치에 정말 x가 있으면 존재

Step 5: "답을 이분한다 — 최적화 문제를 결정 문제로"

지금까지는 '정렬된 배열' 안에서 값을 찾았습니다. 이제 오늘의 반전이에요. 배열이 아예 없는데도 이진 탐색을 쓰는, 매개변수 탐색(parametric search)입니다.

문제부터 봅시다. 길이가 제각각인 랜선 몇 개를 잘라 똑같은 길이의 조각 N개를 만들려고 해요. 이때 만들 수 있는 조각의 '최대 길이'는 얼마일까요? 이런 걸 최적화 문제라고 합니다. 곧장 풀려고 하면 막막해요. 길이를 1부터 하나씩 다 넣어 보면 되지만, 답이 수억이면 그 방법은 시간 초과입니다.

여기서 발상을 뒤집습니다. '가장 긴 길이'를 곧장 구하는 대신, 이렇게 물어봐요. "길이 L로 자르면 조각이 N개 이상 나오나?" 이건 예/아니오로 답하는 결정 문제입니다. 특정 L 하나만 주어지면, 각 랜선을 L로 나눠(랜선 길이 // L) 조각 수를 더해 N과 견주기만 하면 되니 아주 쉬워요.

그런데 이 예/아니오에 결정적인 성질이 하나 숨어 있습니다. L을 키우면 조각 수는 줄기만 해요(조각이 길어지니 개수는 적어지죠). 그래서 어떤 경계까지는 계속 '된다(O)'가 나오다가, 그 경계를 넘는 순간부터 쭉 '안 된다(X)'가 나옵니다. 이렇게 O와 X가 딱 한 번만 갈리는 걸 단조성(monotonic)이라고 해요.

 "길이 L로 자르면 11개 이상 나오나?" — L이 커질수록 조각은 준다(단조)

   L =  ... 198  199  200 | 201  202  ...
   판정      O    O    O   |  X    X          ← O(된다)와 X(안 된다)가 딱 한 번 갈린다
                      └ 되는 L 중 최댓값 = 200 (정답)

   "가장 긴 L?"(최적화)  →  "L로 자르면 11개 나오나?"(결정 O/X)

O와 X가 한 번만 갈린다는 건, 그 경계를 이진 탐색으로 찾을 수 있다는 뜻입니다. 정렬된 배열에서 값을 찾던 것과 똑같아요. 다만 이번엔 배열이 아니라 '답이 될 수 있는 값의 범위(1부터 최대 랜선 길이까지)'를 절반씩 좁힙니다. 가운데 길이를 판정해서 '되면' 더 길게, '안 되면' 더 짧게 밀어붙이는 거죠. 이게 답 자체를 이분한다는 매개변수 탐색의 정체입니다.

🎯 코테에서는 "최대/최소 ○○를 구하라"인데 그 값을 직접 구하기는 어렵고, "특정 값이면 조건을 만족하나?"는 쉽게 판정되며 그 판정이 단조로우면 — 이 세 박자가 보이면 매개변수 탐색입니다. 랜선 자르기, 나무 자르기, 예산 배정이 전부 이 틀이에요.

💡 한 줄 정리

매개변수 탐색은 풀기 어려운 최적화 문제("최대 L?")를 쉬운 결정 문제("L이면 되나?")로 바꾸고, 그 판정이 단조로우면 답의 범위를 이진 탐색으로 좁혀 O(log(범위)×판정비용)에 푼다.

Step 6: "랜선 자르기로 굳히기 — 매개변수 탐색 구현"

개념을 코드로 옮겨 봅시다. 답의 범위는 길이 1부터 max(cables)까지예요(가장 긴 랜선보다 길게는 못 자르니까요). 이 범위를 이진 탐색으로 좁힙니다.

# algorithms/binary_search.py
def max_cut_length(cables, n):
    lo, hi = 1, max(cables)
    best = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        pieces = sum(c // mid for c in cables)   # 길이 mid로 자를 때 나오는 조각 수
        if pieces >= n:                          # 충분하다 → 더 길게 잘라 본다
            best = mid
            lo = mid + 1
        else:                                    # 모자란다 → 더 짧게
            hi = mid - 1
    return best

Step 5의 그림이 그대로 코드가 됐어요. pieces가 판정 함수입니다. 길이 mid로 자를 때 나오는 조각 수를 세서 n과 견줘요. 충분하면(pieces >= n) 답을 더 키울 여지가 있으니 mid를 일단 best에 기록해 두고 lo를 올려 더 긴 쪽을 봅니다. 모자라면 hi를 내려 더 짧은 쪽을 봐요.

여기서 눈여겨볼 건 best에 따로 기록한다는 점입니다. 기본 이진 탐색은 값을 찾으면 바로 반환했지만, 매개변수 탐색은 '되는 것 중 최댓값'을 원해요. 그래서 '될 때마다' 그 값을 후보로 저장해 두고 계속 더 큰 값을 노립니다. 반복이 끝나면 마지막으로 저장된 best가 정답이에요.

 max_cut_length([802, 743, 457, 539], 11)   — 답 L을 [1, 802]에서 이분

   lo=1,   hi=802 → mid=401 → 조각 2+1+1+1 = 5  < 11  → 짧게 (hi=400)
   lo=1,   hi=400 → mid=200 → 조각 4+3+2+2 = 11 >= 11 → 기록 best=200, 길게 (lo=201)
   lo=201, hi=400 → mid=300 → 조각 2+2+1+1 = 6  < 11  → 짧게 (hi=299)
   ... 계속 좁히면 lo > hi, 최종 best = 200

실제로 max_cut_length([802, 743, 457, 539], 11)은 200을 돌려줍니다. 답의 범위가 최대 802라 이진 탐색은 약 10번, 매번 랜선 K개를 훑어 판정하니 전체는 O(log(max) × K)예요. 1부터 하나씩 넣어 보는 O(max × K)와는 하늘과 땅 차이입니다.

이 틀의 진짜 힘은 '판정 함수만 갈아 끼우면' 다른 문제도 똑같이 풀린다는 거예요. 예를 들어 나무 자르기(절단기 높이 H로 잘라 얻는 나무 총량이 M 이상인 최대 H)는 판정 한 줄만 바뀝니다.

        harvested = sum(t - mid for t in trees if t > mid)

랜선의 pieces = sum(c // mid ...)를 이 harvested로 바꾸고, "많이 얻으면 절단기를 높이고, 모자라면 낮춘다"로 방향만 맞추면 끝이에요. 코드베이스 max_tree_cut_height가 바로 그렇게 돼 있고, max_tree_cut_height([20, 15, 10, 17], 7)은 15를 돌려줍니다. 골격은 그대로, 판정만 바뀐 겁니다.

🎯 코테에서는 랜선 자르기·나무 자르기·예산 배정이 매개변수 탐색의 3대 단골입니다. 셋 다 뼈대(답의 범위를 이분 + best 기록)는 똑같고 판정 함수만 달라요. "최댓값을 최대로" 또는 "최솟값을 최소로"가 보이면 이 틀을 꺼내 판정 함수부터 설계하세요. 예산 배정은 오늘 과제로 직접 풀어 봅니다.

💡 한 줄 정리

매개변수 탐색은 답의 범위를 [1, max]로 잡아 이진 탐색하되, '될 때마다' best에 기록해 최댓값을 남기며, 판정 함수만 갈아 끼우면 랜선·나무·예산이 같은 틀로 풀린다.

Step 7: "정리 — 세 가지 이진 탐색 + 언제 쓰나"

오늘 이진 탐색을 세 가지 모습으로 만났습니다. 겉보기엔 달라 보여도 뿌리는 하나, '절반을 확실히 버린다'예요. 한 표로 정리해 봅시다.

세 가지를 관통하는 판단 기준도 정리해 두죠. 정렬된 배열에서 값을 찾거나 경계를 셀 거면, 실전에선 bisect 두 줄이면 됩니다. 원리를 물어보는 면접이나, bisect로는 안 되는 변형(매개변수 탐색처럼 판정이 배열 밖에 있는 경우)에서는 직접 짜야 하고요. 그래서 오늘 세 가지를 다 손으로 짜 본 겁니다.

빅오도 다시 새겨 둡시다. 이진 탐색의 O(log n)은 정말 강력해요. n이 10억이어도 30번, 1조여도 40번입니다. 그래서 "입력이 크고 정렬돼 있다"거나 "답의 범위가 넓지만 판정은 쉽고 단조롭다"가 보이면, 이진 탐색으로 지수적인 크기를 로그로 눌러 버릴 수 있는지 가장 먼저 의심해 보세요.

💡 한 줄 정리

이진 탐색은 값 찾기(기본)·경계 찾기(lower/upper)·답 찾기(매개변수) 세 가지로 쓰이며, 공통 뿌리는 '절반을 확실히 버린다'이고 O(log n)으로 큰 입력을 눌러 준다.

마무리

오늘은 정렬이라는 발판 위에 첫 무기를 올렸습니다. 정렬된 배열을 절반씩 버려 O(log n)에 찾는 이진 탐색을 손으로 짰고, 값이 아니라 경계를 찾는 lower/upper bound와 그 실전판 bisect까지 익혔어요. 그리고 마지막엔 '답 자체를 이분한다'는 매개변수 탐색으로, 최적화 문제를 예/아니오 결정 문제로 바꾸는 발상까지 나아갔습니다.

오늘 배운 핵심 세 가지

• 💡 하나 — 이진 탐색은 절반을 버린다. 정렬된 배열이라는 전제 위에서 가운데를 찍어 후보를 반씩 줄이면 O(log n). n이 10억이어도 30번이면 끝난다. 대신 경계(off-by-one) 처리가 정확성의 전부다.
• 💡 둘 — 값이 아니라 경계를 찾을 수 있다. lower/upper bound는 '이상/초과가 처음인 위치'를 O(log n)에 찾고, 두 경계의 폭이 곧 값의 개수다. 실전에선 bisect_left·bisect_right로 끝난다.
• 💡 셋 — 답 자체를 이분한다. 매개변수 탐색은 어려운 최적화 문제를 쉬운 결정 문제로 바꾼 뒤, 판정이 단조로우면 답의 범위를 이진 탐색으로 좁힌다. 랜선·나무·예산이 같은 틀이다.

다음 시간 예고

오늘 이진 탐색은 '정렬된 배열'을 절반씩 좁혀 O(log n)에 찾았죠. 다음 시간(D-4)엔 정렬된 배열을 이번엔 '양 끝에서' 조여 들어가는 투 포인터를 배웁니다. 두 개의 손가락을 배열 양쪽에 두고 안쪽으로 좁히면, 이중 반복문 O(n²)로 풀던 '두 수의 합' 같은 문제를 단번에 O(n)으로 끌어내려요. 나아가 창문을 미끄러뜨리듯 구간을 훑는 슬라이딩 윈도우, 미리 더해 두고 빼서 쓰는 누적합까지, 'O(n)으로 구간을 다루는' 무기들을 손에 넣습니다. 오늘 정렬이 이진 탐색의 발판이었듯, 정렬은 투 포인터의 발판이기도 합니다.

과제

오늘 배운 경계 탐색(lower/upper bound)과 매개변수 탐색을 손에 붙이는 문제들입니다. 코드베이스 algorithms/binary_search.py의 함수를 가져다 쓰거나, 직접 이진 탐색을 짜서 풀어 보세요. 각 문제의 시간·공간 복잡도를 빅오로 함께 적는 걸 잊지 마세요.

[기초] 삽입 위치 찾기

정렬된 정수 리스트 arr와 값 target이 주어질 때, target이 배열에 있으면 그 위치를, 없으면 정렬을 유지한 채 끼워 넣을 위치를 반환하는 search_insert_position(arr, target)을 작성하세요. 예를 들어 search_insert_position([1, 3, 5, 6], 5)는 2, search_insert_position([1, 3, 5, 6], 2)는 1(1과 3 사이), search_insert_position([1, 3, 5, 6], 7)은 4(맨 뒤)를 반환합니다.

• 이 문제는 오늘 배운 경계 탐색 하나면 끝납니다. '있으면 그 위치, 없으면 삽입 위치'가 어느 경계와 정확히 같은지 떠올려 보세요.
• 선형으로 훑으면 O(n), 이진 탐색으로 하면 O(log n)입니다. 왜 그런지 한 줄로 설명하세요.

[응용] 범위 안의 개수 세기

정렬된 정수 리스트 arr와 두 값 lo_val, hi_val이 주어질 때, lo_val 이상 hi_val 이하인 원소의 개수를 반환하는 count_in_range(arr, lo_val, hi_val)을 작성하세요. 예를 들어 arr = [1, 2, 2, 3, 5, 7]에서 count_in_range(arr, 2, 5)는 4(2, 2, 3, 5)를, count_in_range(arr, 8, 9)는 0을 반환합니다.

• 하나씩 세면 O(n)이지만, 경계 두 번이면 O(log n)입니다. 오늘 배운 lower_bound와 upper_bound를 어떻게 조합할지 생각해 보세요.
• 어떤 경계에 lo_val을 넣고 어떤 경계에 hi_val을 넣어야 '이상 ~ 이하'가 정확히 세어지는지가 핵심입니다.

[심화] 예산 배정 상한 구하기

각 지방의 요청 예산 리스트 requests와 총예산 total이 주어집니다. 상한액을 하나 정해서, 요청액이 상한보다 크면 상한만큼만, 작으면 요청액 그대로 배정합니다. 배정 총합이 total을 넘지 않는 '최대 상한액'을 반환하는 max_budget_cap(requests, total)을 작성하세요(백준 예산 문제). 단, 모든 요청의 합이 total 이내라면 상한이 필요 없으니 가장 큰 요청액을 반환합니다. 예를 들어 max_budget_cap([120, 110, 140, 150], 485)는 127입니다.

• 매개변수 탐색입니다. "상한을 cap으로 두면 배정 총합이 total 이내인가?"라는 결정 문제로 바꿔 보세요. 이 판정은 cap이 커질수록 어느 방향으로 단조로운가요?
• 답의 범위(lo, hi)를 먼저 확정하고, '되면 상한을 올리고 안 되면 내리는' 방향을 정하세요. 요청 합이 예산 이내인 예외 케이스도 잊지 마세요.

생각해볼 주제

1. 이진 탐색은 왜 정렬을 전제로 할까, 그리고 언제 정렬 비용이 아깝지 않을까?

이진 탐색은 O(log n)으로 빠르지만, 정렬돼 있지 않으면 못 씁니다. 정렬을 먼저 하면 O(n log n)이 드는데, 이건 선형 탐색 O(n)보다 오히려 비싸요. 그렇다면 "정렬 후 이진 탐색"이 "그냥 선형 탐색"을 이기는 건 정확히 어떤 상황일까요? '탐색을 몇 번 반복하느냐'를 기준으로, 정렬 비용을 언제 감수할 만한지 따져 보세요. 이 감각은 자료구조 선택(정렬 배열 vs 해시)에서도 똑같이 쓰입니다.

2. 경계 탐색은 왜 닫힌 구간이 아니라 반열린 구간으로 짤까?

기본 이진 탐색은 닫힌 구간 [lo, hi]에 lo <= hi로 짰고, 경계 탐색(lower/upper bound)은 반열린 구간 [lo, hi)에 lo < hi, hi = len(arr)로 짰습니다. 왜 굳이 두 스타일을 나눴을까요? 경계 탐색을 굳이 닫힌 구간으로 짜면 어떤 실수가 생기기 쉬운지, 반열린 구간이 off-by-one을 왜 덜 틀리게 만드는지 생각해 보세요. "경계를 하나 옮겨도 답이 맞으려면 어떤 불변식(invariant)이 유지돼야 하는가"가 힌트입니다.

3. 아무 최적화 문제나 매개변수 탐색으로 풀 수 있을까?

매개변수 탐색은 "최대/최소 답을 이분한다"는 강력한 틀이지만, 아무 문제에나 통하지는 않습니다. 이 틀이 성립하려면 판정 함수가 반드시 '단조로워야' 해요. 어떤 문제가 단조롭고 어떤 문제가 그렇지 않은지, 단조성이 깨지면 왜 이진 탐색이 엉뚱한 답을 내는지 예를 들어 설명해 보세요. "L이면 되는데 L보다 작은 어떤 값은 안 된다"가 가능한 문제라면 어떤 일이 벌어질지 상상해 보면 감이 옵니다.