[LeetCode-1011] 탐색 상한을 "최댓값"으로 잡으면 안 되는 이유 - 파라메트릭 서치의 탐색 범위 설계

Posted Sep 14, 2026 Updated Sep 14, 2026

By Yuchan Kim

13 min read

이진 탐색 개념과 패턴 정리는 카테고리 총정리 글에서 다룬다.

문제 링크: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
파일 경로: src/main/java/coding_test/이진탐색/LC1011_CapacityToShipPackagesWithinDDays.java
난이도: Medium

먼저 밝혀둘 게 있다. 이 문제는 혼자 힌트 없이 푼 게 아니다. 여러 번 틀리는 과정 자체는 전부 내가 직접 겪은 것이지만, 마지막 결정적인 원인(탐색 상한 설정 오류)은 결국 힌트를 받고서야 알았다. 그래도 그 과정에서 뭘 몰랐는지는 뚜렷해졌다.

문제 설명

컨베이어 벨트 위에 짐이 순서대로 놓여 있고, days일 안에 전부 배로 실어 날라야 한다. 매일 짐을 순서대로 배에 싣는데(순서를 바꿀 수 없다), 그날 실은 무게 합이 배의 최대 적재 용량(capacity)을 넘을 수 없다. days일 안에 모든 짐을 다 실어 나를 수 있는 최소 capacity를 구하라.

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

875(Koko Eating Bananas)와 같은 “최댓값의 최솟값을 구하라”는 파라메트릭 서치 문제지만, 각 원소를 독립적으로 계산하는 게 아니라 순서를 지키면서 그룹으로 묶어야 한다는 조건이 하나 더 붙어있다.

시행착오

1차 — 875 패턴을 그대로 복붙

  
long total = 0;
for (int i = 0; i < weights.length; i++) {
    total += (weights[i] + mid - 1) / mid;
}

875에서 썼던 “각 원소를 독립적으로 올림 나눗셈”하는 공식을 그대로 가져왔다. 틀렸다. 875는 무더기 하나를 다 먹는 데 걸리는 시간을 독립적으로 더할 수 있지만, 1011은 짐을 쪼갤 수 없고 여러 짐을 하루에 같이 실을 수도 있다. 문제 구조가 다르면 공식도 다시 설계해야 한다는 걸 깨달았다.

2차 — 총합을 capacity로 나누기

  
total += weights[i];  // 전체 합
total /= mid;

weights = [10, 10], capacity = 15로 손으로 확인해보니, 총합(20)을 15로 나누면 1일인데 실제로는 짐을 쪼갤 수 없어서 2일이 걸린다. “총합 ÷ capacity”는 짐이 무한히 쪼개진다고 가정한 계산이라 안 맞았다.

3차 — 순서대로 누적하다 넘치면 다음 날 (그리디 시뮬레이션)

방향은 맞았지만 세부 버그가 계속 나왔다.

버그 A: total이 하루가 끝나도 리셋이 안 돼서 계속 누적됨
버그 B: 반복문이 weights.length - 1까지만 돌아서 마지막 원소가 처리 안 됨
버그 C: 짐 하나(weights[i])가 그 자체로 capacity(mid)보다 큰 경우, 넘친 걸 되돌리고(i--) 다시 시도해도 또 넘쳐서 무한 루프에 빠짐
버그 D: 반복문이 끝났는데 total에 아직 안 실은 짐이 남아있으면, 그 마지막 날이 카운트에 안 들어감 (항상 실제보다 1일 적게 계산됨)
버그 E: 가능/불가능 판정 후 left/right 갱신 방향이 반대로 되어 있었음 — “가능하면 right = mid(후보 유지), 불가능하면 left = mid + 1(버림)”이 맞는데 반대로 짜져 있었음

이 다섯 개를 하나씩 고치고 나서도 예제 대부분이 계속 틀렸다.

4차 — 탐색 상한(`right`)이 원천적으로 잘못됨

로직을 다 고쳤는데도 결과가 항상 정답보다 낮게 나왔다. 원인은 right를 max(weights)로 잡은 것이었다.

  
int right = weights[0];
for (int w : weights) {
    if (w > right) right = w;   // 최댓값
}

weights = [1..10]의 정답은 15인데, max(weights)는 10이다. 탐색 범위(1~10) 안에 정답(15)이 아예 들어있지도 않았다. 이진 탐색이 아무리 정확해도, 탐색 범위 밖의 값은 절대 찾을 수 없다.

875(Koko)에서는 right = max(piles)가 맞았다 — “속도를 아무리 빠르게 해도 가장 큰 무더기 하나를 1시간에 다 먹는 것 이상은 의미가 없다”는 논리였다. 근데 1011은 하루에 여러 짐을 동시에 실어야 해서, 최악의 경우(모든 짐을 하루에 다 실어야 할 때) capacity가 sum(weights)까지 필요할 수 있다. 그래서 상한을 sum(weights)로 바꿔야 했다.

  
int right = 0;
for (int w : weights) right += w;   // 합

이걸 바꾸자 모든 예제가 통과했다.

최종 코드

  
public static int shipWithinDays(int[] weights, int days) {
    int left = 1;
    int right = 0;
    for (int w : weights) right += w;

    while (left < right) {
        int mid = left + (right - left) / 2;
        int total = 0;
        int numDays = 0;

        for (int i = 0; i < weights.length; i++) {
            if (mid < weights[i]) {
                numDays = days + 1;  // 이 mid로는 애초에 불가능
                break;
            }
            total += weights[i];
            if (total == mid) {
                numDays++;
                total = 0;
            } else if (total > mid) {
                numDays++;
                total = weights[i];
            }
        }
        if (total > 0) numDays++;   // 마지막 날 반영

        if (numDays <= days) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

추적표 (예제 1: weights=[1..10], days=5)

반복	left	right	mid	numDays 계산 결과	판정	다음 동작
1	1	55	28	2	가능	right = 28
2	1	28	14	6	불가능	left = 15
3	15	28	21	4	가능	right = 21
4	15	21	18	5	가능	right = 18
5	15	18	16	5	가능	right = 16
6	15	16	15	5	가능	right = 15
-	15	15	-	-	종료	return 15

(right를 처음에 max(piles)=10으로 잘못 잡았을 때는 이 표의 시작 범위 자체가 1~10이라 15가 후보에 들어올 수조차 없었다.)

오늘 배운 내용

이진 탐색의 탐색 상한(right)은 “배열에서 뽑아낸 최댓값”이 아니라, “문제의 정의상 확실히 답이 될 수 있는 값”이어야 한다.

875에서는 max(piles)가 그 조건을 만족했다(속도가 그것보다 빠를 이유가 없으니까). 1011에서는 하루에 여러 짐을 같이 실을 수 있다는 조건 때문에, 필요한 capacity가 배열의 최댓값을 넘어설 수 있다 — 그래서 sum(weights)가 진짜 상한이다. “이 문제에서 절대적으로 안전한 상한이 뭔가”를 문제마다 새로 따져봐야 한다.

오답노트

틀렸던 패턴 1: 875의 “각 원소 독립 계산” 공식을 그대로 재사용. 왜 틀렸나: 875는 원소가 서로 독립이지만 1011은 순서를 지키며 그룹으로 묶어야 해서 구조가 다르다. 다음에 떠올릴 시점: 비슷해 보이는 문제라도 “원소들이 서로 독립인가, 순서/그룹 제약이 있는가”부터 확인한다.
틀렸던 패턴 2: total 리셋 누락, 마지막 원소 미처리, 짐 하나가 capacity 초과할 때 무한 루프. 왜 틀렸나: “하루 단위로 끊어서 세는” 시뮬레이션을 정확히 설계하지 않고 즉흥적으로 조건을 덧붙이면서 생긴 문제들. 다음에 떠올릴 시점: 그리디 시뮬레이션을 짤 때는 “하루가 시작되는 조건”, “하루가 끝나는 조건”, “루프가 끝난 뒤 남은 하루는 어떻게 되는가”를 먼저 말로 정리하고 코드로 옮긴다.
틀렸던 패턴 3: 판정 성공/실패 시 left/right 갱신 방향이 반대. 왜 틀렸나: “가능하면 더 줄여본다(right=mid), 불가능하면 버린다(left=mid+1)”는 불변식을 급하게 짜다가 헷갈림. 다음에 떠올릴 시점: 파라메트릭 서치 코드를 짤 때마다 이 문장을 소리 내어 확인한다.
틀렸던 패턴 4 (가장 크게 틀렸던 것): 탐색 상한을 max(weights)로 설정. 왜 틀렸나: 875의 상한 설정 논리를 별생각 없이 그대로 가져왔다. 문제마다 “정답이 확실히 이 값 이하다”라는 논리는 다시 세워야 한다. 다음에 떠올릴 시점: 파라메트릭 서치 문제를 새로 만날 때마다, left/right 초기값을 정하고 나서 “이 상한이 진짜로 항상 가능한 값인가?”를 예제로 한 번 검증한다.

꿀팁

파라메트릭 서치에서 탐색 범위(left/right)의 초기값을 정할 때는 “이 값이면 무조건 성공한다” / “이 값보다 작으면 무조건 실패한다”는 근거를 문장으로 먼저 말해보는 게 좋다. 근거가 안 서면 그 값은 상한/하한으로 쓰면 안 된다.
하루/구간 단위로 묶는 그리디 시뮬레이션을 짤 때는 total > 0으로 “마지막에 처리 안 된 게 남았는지”를 항상 체크한다. 반복문이 딱 맞아떨어지지 않는 이상 마지막 조각이 남는 경우가 흔하다.

알고리즘 연습, 이진탐색

This post is licensed under CC BY 4.0 by the author.