Coding Interview Prep · 강의

답 공간 이진 검색

Q: “답 공간 이진 검색” 강의는 무료인가요?

네 — “답 공간 이진 검색” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

Q: “답 공간 이진 검색” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

연속적인 답의 범위를 검색 공간으로 간주해 minimum-time-to-complete-jobs와 capacity-to-ship-packages 같은 문제를 해결합니다.

답 공간 이진 검색은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

정답 공간에서의 이진 탐색

대부분의 사람은 정렬된 배열에서 값을 찾는 이진 탐색을 알고 있습니다. 하지만 이진 탐색은 가능한 답의 공간에 적용할 때 더욱 강력합니다. 배열을 탐색하는 대신 숫자 범위를 탐색합니다. 예를 들어 '모든 소포를 배송하는 데 필요한 최소 일수는 얼마인가?'와 같은 문제를 풀면서, 확인 함수를 사용해 후보 답이 실현 가능한지 판단합니다.

이 기법을 사용하면 많은 최적화 문제의 복잡도를 O(n²) 이상에서 O(n log(max_answer))로 낮출 수 있습니다.

정답 공간 템플릿

템플릿은 세 가지 구성 요소로 이루어집니다. 첫째, 모든 유효한 답을 포함하도록 탐색 범위 [lo, hi]를 정합니다. 둘째, 중간값을 달성할 수 있으면 참을 반환하는 실현 가능성 확인 can_achieve(mid)를 작성합니다. 셋째, [lo, hi]에서 이진 탐색을 수행합니다. can_achieve(mid)가 참이면 더 작은(또는 더 큰) 답을 향해 이동하고, 그렇지 않으면 반대 방향으로 이동합니다.

핵심 속성은 실현 가능성 함수가 단조적이어야 한다는 것입니다. 어떤 답이 실현 가능해진 뒤에는 그보다 큰 모든 값도 실현 가능하거나, 그보다 작은 모든 값이 실현 불가능해야 합니다.

# Generic template
def answer_space_search(lo, hi, is_feasible):
    result = hi  # or lo, depending on direction
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            result = mid
            hi = mid - 1   # try to minimise further
        else:
            lo = mid + 1
    return result

예시: 패키지 배송 용량

LeetCode 1011 'D일 안에 패키지를 배송할 수 있는 용량': 가중치 목록과 D일이 주어졌을 때, 모든 패키지를 순서대로 D일 안에 배송하기 위한 최소 배송 용량을 찾습니다. 답은 [max(weights), sum(weights)] 범위에 있습니다. 탐욕적 시뮬레이션으로 모든 패키지를 D일 안에 배송할 수 있으면 해당 용량은 가능합니다. 용량 범위에 이분 탐색을 적용하면 O(n log(sum)) 시간에 해결할 수 있습니다.

def shipWithinDays(weights, days):
    def can_ship(capacity):
        needed_days, current_load = 1, 0
        for w in weights:
            if current_load + w > capacity:
                needed_days += 1
                current_load = 0
            current_load += w
        return needed_days <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(mid):
            hi = mid        # feasible, try smaller
        else:
            lo = mid + 1    # not feasible, need more capacity
    return lo

print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5))  # 15
print(shipWithinDays([3,2,2,4,1,4], 3))            # 6

예시: 코코의 바나나 먹기

LeetCode 875 '코코의 바나나 먹기': 코코는 시간당 K개의 바나나를 먹을 수 있으며, H개의 바나나 더미를 정확히 H시간 안에 모두 먹으면서 K를 최소화하려고 합니다. 탐색 범위는 [1, max(piles)]입니다. 검사 방법은 다음과 같습니다. 속도가 K이면 총 소요 시간은 sum(ceil(pile/K))이고, 이 값은 <= H여야 합니다. 이 조건을 만족하는 가장 작은 K를 이분 탐색으로 찾습니다.

import math

def minEatingSpeed(piles, h):
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid      # feasible, try lower speed
        else:
            lo = mid + 1  # too slow
    return lo

print(minEatingSpeed([3,6,7,11], 8))    # 4
print(minEatingSpeed([30,11,23,4,20], 5))  # 30

예시: 꽃다발을 만드는 데 필요한 최소 일수

LeetCode 1482 'm개의 꽃다발을 만드는 데 필요한 최소 일수': m개의 꽃다발이 필요하며, 각 꽃다발은 서로 인접한 k송이의 꽃으로 구성됩니다. 꽃 i는 bloomDay[i]일에 핍니다. 날짜를 기준으로 이분 탐색합니다. 범위는 1일부터 bloomDay의 최댓값까지입니다. 가능성 검사에서는 연속해서 핀 꽃의 수를 세고 m개의 꽃다발을 만들 수 있는지 확인합니다. 단조성: d일에 가능하다면 d+1일에도 가능합니다.

def minDays(bloomDay, m, k):
    if m * k > len(bloomDay):
        return -1  # impossible

    def can_make(day):
        bouquets = consecutive = 0
        for bd in bloomDay:
            if bd <= day:
                consecutive += 1
                if consecutive == k:
                    bouquets += 1
                    consecutive = 0
            else:
                consecutive = 0
        return bouquets >= m

    lo, hi = 1, max(bloomDay)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_make(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(minDays([1,10,3,10,2], 3, 1))  # 3
print(minDays([1,10,3,10,2], 3, 2))  # -1

탐색 범위 찾기

올바른 [lo, hi] 범위를 선택하는 것이 중요합니다. lo는 가능한 답 중 최솟값이어야 하며(예: 최솟값, 1 또는 0), hi는 가능한 답 중 최댓값이어야 합니다(예: 모든 요소의 합, 최댓값 또는 n). hi를 너무 작게 설정하면 유효한 답을 놓치지만, 너무 크게 설정하는 것은 괜찮습니다. 이분 탐색은 O(log(hi - lo)) 단계 안에 수렴하기 때문입니다.

# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating:      lo=1,            hi=max(piles)
# Square root:      lo=1,            hi=x
# Allocate books:   lo=max(pages),   hi=sum(pages)

def isqrt_bs(x):
    if x < 2:
        return x
    lo, hi = 1, x
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if mid * mid <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo - 1

for n in [0, 1, 4, 8, 9, 15, 16]:
    print(f'isqrt({n}) = {isqrt_bs(n)}')

최댓값 찾기와 최솟값 찾기: 방향이 중요합니다

답의 공간에서 수행하는 이분 탐색에는 두 가지 방식이 있습니다. 답의 최솟값 찾기: 검사에 통과하면 더 작은 값을 시도하고(hi = mid), 통과하지 못하면 더 큰 값을 시도합니다(lo = mid + 1). 답의 최댓값 찾기: 검사에 통과하면 더 큰 값을 시도하고(lo = mid + 1, mid를 후보로 저장), 통과하지 못하면 더 작은 값을 시도합니다(hi = mid - 1). 코드를 작성하기 전에 어느 방향으로 탐색할지 항상 명확히 정해야 합니다.

# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
    result = lo - 1   # sentinel: no feasible answer found
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            result = mid
            lo = mid + 1  # try larger
        else:
            hi = mid - 1
    return result

# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50))  # 7

최소 페이지 할당(대표 문제)

페이지 수 배열을 가진 n권의 책과 k명의 학생이 주어졌을 때, 가장 많은 페이지를 읽는 학생의 페이지 수가 최대한 적어지도록 책을 연속된 구간으로 할당합니다. 답, 즉 가능한 최댓값의 최솟값에 대해 이분 탐색합니다. 가능성 검사에서는 책을 탐욕적으로 학생들에게 할당합니다. 책을 하나 더 할당하면 현재 최댓값을 초과할 때 새 학생에게 그 책을 할당합니다. 필요한 학생 수가 <= k이면 해당 최댓값을 달성할 수 있습니다.

def allocate_min_pages(pages, k):
    if k > len(pages):
        return -1

    def is_feasible(max_pages):
        students, current = 1, 0
        for p in pages:
            if p > max_pages:
                return False  # single book exceeds limit
            if current + p > max_pages:
                students += 1
                current = 0
            current += p
        return students <= k

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

print(allocate_min_pages([12, 34, 67, 90], 2))  # 113
print(allocate_min_pages([10, 20, 30, 40], 2))  # 60

답의 공간 탐색의 복잡도 분석

시간 복잡도는 O(n × log(range))입니다. 여기서 n은 가능성 검사의 비용(대개 선형 순회)이고, 탐색 범위의 크기는 hi - lo입니다. 예를 들어 페이지 합계가 10⁹이고 가능성 검사가 O(n)이면 전체 시간은 O(n log 10⁹) ≈ O(30n)입니다. 이는 완전 탐색의 O(n²)보다 훨씬 빠릅니다.

공간 복잡도는 이분 탐색 자체에 대해 O(1)이며, 여기에 가능성 검사에서 사용하는 공간이 더해집니다.

import math

# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9         # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9)  # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')

정렬된 행렬에서 k번째로 작은 값

LeetCode 378 '정렬된 행렬에서 k번째로 작은 요소': n×n 행렬의 각 행과 열이 정렬되어 있습니다. 행렬의 왼쪽 위 값부터 오른쪽 아래 값까지의 답 범위에서 이분 탐색합니다. 가능성 검사에서는 왼쪽 아래 모서리에서 시작하는 포인터를 사용해 중간값 이하인 요소의 개수를 O(n) 시간에 셉니다. 중간값 이하인 요소가 k개 이상이 되는 가장 작은 값을 찾습니다.

def kthSmallest(matrix, k):
    n = len(matrix)

    def count_le(mid):
        count, row, col = 0, n - 1, 0
        while row >= 0 and col < n:
            if matrix[row][col] <= mid:
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    lo, hi = matrix[0][0], matrix[n-1][n-1]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if count_le(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8))  # 13

답의 공간 문제 알아보기

답의 공간 이분 탐색에 적합한 문제에는 공통적인 신호가 있습니다. 문제에서 최솟값 또는 최댓값을 요구하고, 답이 범위가 제한된 숫자에 속하며, 후보 답을 증가시키거나(또는 감소시키거나) 하면 가능 여부가 단조롭게 좋아지거나 나빠집니다. 대표적인 표현으로는 '가능한 최댓값 중 최솟값', '최대 k번의 연산', 'd일 이내'가 있습니다.

이러한 신호를 발견하면 즉시 lo와 hi를 정하고, 가능성 함수를 작성한 다음, 이 템플릿을 적용하십시오. 이렇게 구조화된 접근법은 면접에서 거의 실패하지 않습니다.

빠른 확인

이 레슨에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 얼마나 이해했는지 확인해 보십시오.

레슨 요약

이 레슨에서는 다음을 배웠습니다. 가능성 함수가 숫자 범위에서 단조로울 때 답의 공간 이분 탐색을 적용합니다. 이 템플릿은 [lo, hi]를 탐색하며 가능 여부 검사를 사용해 탐색 공간을 절반으로 줄입니다. 또한 전체 복잡도는 O(n log(range))이며, n은 한 번의 가능성 검사를 수행하는 데 드는 비용입니다. 다음에는 연결 리스트와 노드 클래스를 살펴봅니다.

자주 묻는 질문