이진 탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법

✅ 문제

한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력 예시

4 6
19 15 10 17

출력 예시

15

💻 코드

# 1부터 가장 긴 떡의 길이까지 이진 탐색. 중간값을 절단기에 설정한 높이
# target은 요청한 길이 M
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        
        total_length = 0 
        
        for i in array:
            if i > mid:
                total_length += i - mid
        if total_length == target:
            return mid
        # 절단한 떡의 총 길이가 요청한 길이보다 길다면 높이가 더 커야한다.
        elif total_length > target:
            start = mid + 1
        else:
            end = mid - 1
        total_length = 0

N, M = map(int, input().split())

array = list(map(int, input().split()))

print(binary_search(array), 6, 1, max(array))

설계

1부터 가장 긴 떡의 길이까지를 이진 탐색할 노드로 설정하고, 절단기의 높이를 중간값으로 한다. 중간값을 기준으로 잘린 떡의 총 길이와 손님이 요청한 총 길이가 일치하면 중간값을 절단기의 높이로 설정한다.

➕ 문제 풀이

절단기의 높이 H를 반복해서 조정하는 것이 이 문제 풀이의 핵심이다.
순차 탐색도 가능하지만 절단기의 높이는 1부터 2,000,000,000까지 가능하므로 순차 탐색은 시간 초과가 될 것이다.

📝 정리

입력 조건이 1억개가 넘어간다면 순차 탐색보다 이진 탐색을 떠올리자.