완전탐색의 함정에서 파라메트릭 서치로

첫 접근: 완전 탐색

백준 1654번 랜선 자르기 문제를 처음 봤을 때 떠오른 생각은 단순했다.

"가능한 최대 길이부터 시작해서 1씩 줄여가며 확인하면 되지 않을까?"

// 이렇게 하면 되지 않을까?
long maxPossible = Arrays.stream(cables).max().getAsInt();

for (long length = maxPossible; length >= 1; length--) {
    if (canMake(cables, length, N)) {
        return length;  // 처음으로 가능한 길이 = 최댓값!
    }
}

직관적이고 확실한 방법이다. 하지만 제약 조건을 보는 순간 뭔가 이상했다.

K(랜선 개수): 1 ~ 10,000
N(필요한 개수): 1 ~ 1,000,000  
각 랜선 길이: 최대 2³¹-1 (약 21억)

시간복잡도를 계산해보니: O((2³¹-1) × K) = 21억 × 1만 = 21조 번 1초에 1억 번 연산을 가정해도 21만 초... 약 58시간이다. 완전탐색은 불가능했다.

이분 탐색?

완전탐색이 안 된다는 건 알겠는데, 대안이 뭘까? 문제 페이지를 다시 살펴보니 하단에 "알고리즘 분류" 섹션이 있었다.

이분 탐색
매개변수 탐색

"이분 탐색?" 내가 아는 이분 탐색은 정렬된 배열에서 특정 값을 찾는 것인데, 이 문제엔 그런 배열이 없다.

랜선 문제엔 "정렬된 배열"도 없고 "찾을 특정 값"도 없는데, 어떻게 이분 탐색을 적용한다는 걸까? "매개변수 탐색?" 처음 보는 용어여서 찾아보았다.

Prametric Search(매개변수 탐색)이란?

"최적화 문제를 결정 문제로 바꾸어 해결하는 기법"

즉, 어떤 조건의 최댓값/최솟값을 찾아라 라는 문제를 이 값이 조건에 맞는가?(YES/NO) 라는 질문으로 바꾸어 이분 탐색을 적용하는 것이다.

문제가 요구하는 것을 한 문장으로 표현하면 "K개의 랜선을 N개의 랜선을 만들기 위해 K개의 각 랜선의 길이는 몇으로 맞춰야 하나?" 다.

최적화 문제: "N개를 만들 수 있는 랜선의 최대 길이는 얼마인가?"
결정 문제: "길이가 X일 때, 랜선을 N개 이상 만들 수 있는가?"

최적화 문제는 답을 직접 구하기 어렵지만, 결정 문제는 간단한 반복문으로 검증할 수 있다:

// 길이 X로 N개 이상 만들 수 있나?
boolean canMake(int[] cables, int length, int N) {
    int count = 0;
    for (int cable : cables) {
        count += cable / length;
    }
    return count >= N;  // O(K) - 금방 확인 가능
}

이래서 이분 탐색을 쓰는구나? 결정 문제로 바꾸면 "가능한 길이 범위"에서 이분 탐색을 할 수 있다. 배열이 아니라 답의 범위를 이분 탐색하는 거였다.

성립 조건: 단조성

모든 최적화 문제를 결정 문제로 바꿀 수 있는 건 아니었다. 단조성(Monotonicity)이라는 조건이 필요했다.

랜선 문제에서 길이와 생산 개수의 관계:

길이 100 으로 자르면: 50개 만들어짐 (true)
길이 200 으로 자르면: 25개 만들어짐 (true)
길이 300 으로 자르면: 11개 만들어짐 (true) -> 문제가 원하는 답
길이 400 으로 자르면: 10개 만들어짐 (false)
길이 500 으로 자르면: 8개 만들어짐 (false) 패턴:
길이 X에서 N개를 만들 수 있으면 → X보다 짧은 모든 길이에서도 가능
길이 X에서 N개를 못 만들면 → X보다 긴 모든 길이에서도 불가능 TRUE, TRUE, TRUE, FALSE, FALSE... 순서로 일관되게 변한다. 이 일방향성 때문에 이분 탐색으로 경계선(최대 길이)을 찾을 수 있는 거였다.

그래서 어떻게 구현해?

개념은 이해했다. 이제 코드로 옮겨야 했다.

기존 이분 탐색 코드를 보며 뭘 바꿔야 할지 생각했다:

// 정렬된 배열에서 5 찾기
int[] arr = {1, 3, 5, 7, 9};
int left = 0, right = arr.length - 1;

while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] == 5) return mid; // 찾음!
    else if (arr[mid] < 5) left = mid + 1; // 오른쪽 탐색
    else right = mid - 1; // 왼쪽 탐색
}
return -1; // 못찾음

변경 1: 배열 인덱스 → 답의 범위

int[] cables = {802, 743, 457, 539};

// Before: 배열 인덱스 탐색
int left = 0;               
int right = arr.length - 1; 

// After: 가능한 답의 범위 탐색
int left = 1;        // 최소 가능 길이
int right = 802;     // 최대 랜선 길이 (가장 긴 랜선)

변경 2: 값 비교 → 조건 함수

// Before: 배열 값과 비교
if (arr[mid] == 5)

// After: 조건 만족 여부 확인
if (canMake(cables, mid, N))

여기까진 괜찮았다. 하지만 다음 부분에서 막혔다.

변경 3: 찾았을 때 뭘 해야 하지?

while (left <= right) {
    int mid = (left + right) / 2;

    if (canMake(cables, mid, N)) {
        // 조건을 만족한다... 그럼 이제?
        return mid;  // 이렇게 하면 될까?
    }
}

첫 시도: 조건 만족 시 바로 `return`

if (canMake(cables, mid, N)) {
    return mid;  // 가능한 길이를 찾았으니 반환
}

테스트해보니 틀렸다. 예를 들어 길이 200으로 11개를 만들 수 있다고 해서 바로 200을 반환하면, 혹시 길이 300으로도 11개를 만들 수 있는지 확인을 안 하게 된다. 우리가 찾는 건 "조건을 만족하는 최댓값"이다.

수정: 조건 만족해도 계속 탐색

int answer = 0;  // 결과를 저장할 변수

while (left <= right) {
    int mid = (left + right) / 2;

    if (canMake(cables, mid, N)) {
        answer = mid;        // 일단 현재 값 저장
        left = mid + 1;      // 더 큰 값도 가능한지 계속 확인
    } else {
        right = mid - 1;     // 이 값은 안 되니 더 작은 값 시도
    }
}

return answer;  // 최종적으로 찾은 최댓값

이게 일반 이분 탐색과의 가장 큰 차이점이었다.

일반 이분 탐색: 찾으면 즉시 종료
파라메트릭 서치: 찾아도 계속 탐색 (더 나은 답 찾기)

두번째 시도: 런타임 에러

int left = 1;
int right = 802;
int answer = 0;

while (left <= right) {
    int mid = (left + right) / 2;

    if (canMake(cables, mid, N)) {
        answer = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

System.out.println(answer);

왜지? 코드를 다시 보니 canMake 함수에서 문제가 있었다.

boolean canMake(int[] cables, int length, int N) {
    int count = 0;
    for (int cable : cables) {
        count += cable / length;  // length가 0이면?
    }
    return count >= N;
}

left = 1로 시작했으니 length가 0일 일은 없어야 하는데... 아, int 오버플로우 문제였다.

문제

int left = 1;
int right = 802;
int mid = (left + right) / 2;  // 여기까진 괜찮음

// 하지만 랜선 길이가 최대 2³¹-1 (21억)이면?
int right = 2147483647;
int mid = (left + right) / 2;  // left + right가 int 범위 초과!

left + right가 int 범위를 넘어서 음수가 되고, 그걸 2로 나누면 음수 mid가 나와서 0 / length에서 에러가 발생한 거였다.

해결

// Before
int left = 1;
int right = maxCable;
int mid = (left + right) / 2;  // 오버플로우 위험

// After  
long left = 1;
long right = maxCable;
long mid = left + (right - left) / 2;  // 오버플로우 방지

left + (right - left) / 2는 (left + right) / 2와 같은 값이지만, 중간 계산에서 오버플로우가 발생하지 않는다.

최종 구현

import java.io.BufferedReader;  
import java.io.BufferedWriter;  
import java.io.InputStreamReader;  
import java.io.OutputStreamWriter;  
import java.util.StringTokenizer;  

public class Main {  

    public static void main(String[] args) throws Exception {  
       try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
           BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {  

          StringTokenizer st = new StringTokenizer(br.readLine());  
          int K = Integer.parseInt(st.nextToken());  
          int N = Integer.parseInt(st.nextToken());  
          int[] cables = new int[K];  
          for (int i = 0; i < K; i++) {  
             cables[i] = Integer.parseInt(br.readLine());  
          }  

          long left = 1;  
          long right = Integer.MAX_VALUE;  
          long answer = 0;  
          while (left <= right) {  
             long mid = (left + right) / 2;  
             if (canMake(cables, mid, N)) {  
                answer = mid;  
                left = mid + 1;  
             } else {  
                right = mid - 1;  
             }  
          }  
          bw.write(answer + "");  
          bw.flush();  
       }  
    }  

    private static boolean canMake(int[] cables, long length, int N) {  
       long total = 0;  
       for (int cable : cables) {  
          total += cable / length;  
       }  
       return total >= N;  
    }  
}

배운 점

1. 파라메트릭 서치 = 질문을 바꾸기

"최댓값은 무엇인가?"라는 어려운 질문을 "이 값으로 가능한가?"라는 쉬운 질문으로 바꾸면, O(N)을 O(log N)으로 극적으로 개선할 수 있다.

2. 단조성이 핵심

결과가 TRUE, TRUE, FALSE, FALSE... 처럼 일방향으로 변해야 이분 탐색이 가능하다. 이 패턴이 보이면 파라메트릭 서치를 고려하자.

3. "찾아도 계속 탐색"

일반 이분 탐색과 달리, 조건을 만족하는 값을 찾아도 즉시 종료하지 않고 더 나은 답을 계속 찾아야 한다.

4. 구현 디테일도 중요

int vs long: 범위가 크면 반드시 long 사용
중간값 계산: left + (right - left) / 2로 오버플로우 방지
답 저장 변수: answer를 따로 두고 갱신

변화 요약표

항목	Classic Binary Search	Parametric Search
탐색 대상	`arr[0] ~ arr[n-1]`	`1 ~ max` (답의 범위)
left/right 의미	배열 인덱스	가능한 답의 범위
중간값	`arr[mid]`	`mid` (시도할 값)
비교	`arr[mid] == target`	`isValid(mid)`
찾았을 때	`return mid`	`answer = mid; 계속 탐색`
목적	값의 위치	최적값 (최댓값/최솟값)
타입	`int`	`long` (범위 클 때)
결과	인덱스 또는 -1	최적값

🔗GitHub 저장소

해당 글에 작성된 코드는 아래 GitHub 저장소에서 확인할 수 있다.

GitHub 저장소: ps-baekjoon-1654-parametric-search

'알고리즘' 카테고리의 다른 글

Floyd-Warshall (플로이드-워셜) (0)	2026.01.13
Two Pointer (투 포인터) (1)	2026.01.13
DFS/BFS - 그래프 탐색의 두 가지 접근 (0)	2025.12.29

첫 접근: 완전 탐색

이분 탐색?

Prametric Search(매개변수 탐색)이란?

성립 조건: 단조성

그래서 어떻게 구현해?

변경 1: 배열 인덱스 → 답의 범위

변경 2: 값 비교 → 조건 함수

변경 3: 찾았을 때 뭘 해야 하지?

첫 시도: 조건 만족 시 바로 return

수정: 조건 만족해도 계속 탐색

두번째 시도: 런타임 에러

문제

해결

최종 구현

배운 점

1. 파라메트릭 서치 = 질문을 바꾸기

2. 단조성이 핵심

3. "찾아도 계속 탐색"

4. 구현 디테일도 중요

변화 요약표

🔗GitHub 저장소

'알고리즘' 카테고리의 다른 글

티스토리툴바

첫 시도: 조건 만족 시 바로 `return`