코테용 이분탐색은 다르다! 무한 루프 없는 매개 변수 탐색 실전 템플릿

코딩테스트장에서 이분탐색(Binary Search) 문제를 만나면 뇌정지부터 오는 게 정상입니다. 머리로는 while (left <= right)를 돌리면 된다는 걸 알면서도, 막상 문제를 읽어보면 도대체 무엇을 left와 right로 잡아야 할지, 조건문은 어떻게 태워야 할지 손이 안 떨어지기 때문입니다. 이 글은 템플릿만 외우다가 실전에서 매번 뒤통수를 맞는 후배 개발자들을 위해, 코테장에서 바로 써먹을 수 있는 이분탐색의 실전 접근 순서와 뼈대를 가감 없이 공유합니다.

왜 내가 짜는 이분탐색은 실전에서 무한 루프에 빠질까?

수많은 주니어들이 "이분탐색 개념은 쉽죠"라고 했다가 실전 코테에서 피를 봅니다. 책에서 배우는 이분탐색은 이미 예쁘게 오름차순 정렬된 배열에서 특정 숫자 하나를 찾는 간단한 구조이기 때문입니다. 하지만 실제 기업 코딩테스트에 나오는 이분탐색의 90% 이상은 배열에서 인덱스를 찾는 문제가 아니라 '매개 변수 탐색(Parametric Search)'입니다.

 

매개 변수 탐색은 최적화 문제(최솟값이나 최댓값을 구하는 문제)를 결정 문제(이 값이 조건을 만족하는가? Yes or No)로 바꾸어 푸는 기법입니다. 이 개념이 꼬이기 시작하면 실전에서 다음과 같은 고통을 겪게 됩니다.

• left와 right를 한 칸씩 줄여야 할지, 아니면 mid를 포함해야 할지 헷갈려서 while문이 영원히 끝나지 않는 무한 루프에 빠집니다.
• 테스트 케이스는 맞는데 제출하면 '틀렸습니다'를 받습니다. 높은 확률로 최댓값/최솟값 경계선에서 값이 1씩 밀렸기 때문입니다.
• 문제 조건의 데이터 범위가 10억, 100억인데 엉뚱한 곳에서 선형 탐색을 하다가 시간 초과(Time Limit Exceeded)를 마주합니다.

실전 코테용 이분탐색 판단 프로세스 3단계

시험장에서 문제를 만났을 때 바로 키보드에 손을 올리지 마십시오. 다음 3단계 순서대로 문제를 뜯어보고 설계를 끝내야 구현할 때 안 꼬입니다.

1단계: 데이터 범위에서 '대놓고 주는 신호' 포착하기

이분탐색은 시간 복잡도가 $O(\log N)$입니다. 이 말은 문제에서 주어지는 입력 데이터의 범위가 말도 안 되게 크다는 뜻입니다. 예를 들어, 탐색해야 하는 범위나 배열의 특정 값이 10^9(10억) 또는 $10^{18}$처럼 일반적인 $O(N)$이나 O(N \log N) 알고리즘으로 도저히 시간 내에 통과할 수 없는 수치라면 십중팔구 이분탐색, 특히 매개 변수 탐색입니다. "최댓값의 최솟값"이나 "최솟값의 최댓값"을 구하라는 문장까지 붙어 있다면 확신해도 좋습니다.

2단계: '단조성(Monotonicity)' 검증하기

이분탐색을 쓰려면 반드시 '단조성'이 성립해야 합니다. 단조성이란 값이 커질수록 조건 만족 여부가 [참, 참, 참, 거짓, 거짓, 거짓] 혹은 [거짓, 거짓, 참, 참, 참]처럼 한 방향으로만 변하는 성질을 말합니다. 값이 커지다가 도중에 참이 되고, 다시 거짓이 되었다가 참이 되는 구조라면 이분탐색을 절대 쓸 수 없습니다. 내가 잡은 기준값(mid)에 따라 결과가 이분법적으로 똑 떨어지는지 확인하십시오.

3단계: 변수의 역할 정의하기

머릿속으로 다음 세 가지 요소를 문장으로 명확히 정의해야 합니다. 이 작업이 끝나지 않으면 코드는 한 줄도 내려가지 못합니다.

• 무엇을 mid로 잡고 이분탐색을 돌릴 것인가? (예: 랜선의 길이, 입국심사 걸리는 시간)
• 결정 함수(isValid)의 인자로 mid를 넘겼을 때 내부에서 무엇을 기준으로 계산할 것인가? (예: mid 길이로 잘랐을 때 나오는 랜선의 총 개수)
• 탐색 범위의 물리적 극한인 left와 right의 초기값은 무엇인가? (예: left = 1, right = 가장 긴 랜선의 길이)

이분탐색 코드 회로 - 생성형 AI 이미지

실무에서도 통하는 무한 루프 없는 이분탐색 표준 템플릿

경계선 조건 때문에 머리 싸매지 마십시오. 실전에서 소수점 버림 오류나 오프바이원(Off-by-one) 에러를 방지하는 가장 깔끔하고 직관적인 템플릿은 정답 전용 변수(ans)를 따로 두고, 조건이 만족할 때마다 이를 갱신한 뒤 범위를 확실하게 좁히는 방식입니다.

long left = 최소범위;
long right = 최대범위;
long ans = 0; // 혹은 초기값 설정을 문제에 맞게 조절
while (left <= right) {
    long mid = left + (right - left) / 2; // 오버플로우 방지용 스타일
    if (isValid(mid)) {
        ans = mid; // 조건을 만족했으므로 일단 정답 후보로 저장!
        // 최댓값을 구하는 문제라면: 더 큰 값을 찾아 오른쪽 구간 탐색
        left = mid + 1;
        // 만약 최솟값을 구하는 문제라면: 더 작은 값을 찾아 왼쪽 구간 탐색
        // right = mid - 1;
    } else {
        // 조건을 만족하지 못했다면: 범위를 반대로 좁힘
        // 최댓값 문제 기준, mid가 불가능하므로 더 작은 구간 탐색
        right = mid - 1;
        // 최솟값 문제 기준이라면: left = mid + 1;
    }
}
System.out.println(ans);

이 방식의 핵심은 isValid(mid)가 참일 때 ans에 현재의 mid를 안전하게 박아두고, left = mid + 1 또는 right = mid - 1을 통해 mid 자체를 탐색 범위에서 완전히 제외한다는 점입니다. 이렇게 짜면 while문 탈출 조건인 left > right가 완벽하게 보장되므로 절대 무한 루프에 걸리지 않습니다.

"이분탐색 돌릴 배열은 무조건 정렬해야 하나요?"

많은 후배들이 하는 단골 질문입니다. 결론부터 말하자면, "내가 이분탐색을 돌리는 대상이 누구냐"에 따라 다릅니다.

 

주어진 배열 자체에서 무언가를 이분탐색으로 찾으려면 당연히 배열이 정렬되어 있어야 합니다. 하지만 우리가 지금 다루는 매개 변수 탐색에서 이분탐색을 돌리는 대상은 배열이 아니라 "내가 정의한 정답의 후보 범위(정수 공간)"입니다. 예를 들어 가상의 정답 범위가 1부터 10억까지라면, 이 정수 공간 자체가 이미 오름차순으로 정렬된 상태나 다름없습니다.

 

따라서 정답 후보를 뽑아 결정 함수(isValid)에 던져줄 때는 원본 데이터 배열이 정렬되어 있지 않아도 상관없습니다. 다만, isValid 함수 내부에서 그리디(Greedy) 알고리즘이나 투 포인터 등을 쓰기 위해 원본 배열을 정렬해야 하는 경우는 아주 흔합니다. 원본 배열의 정렬 필요성은 이분탐색 자체 때문이 아니라, 순수하게 결정 함수 내부의 로직을 고속화하기 위함이라는 것을 명확히 구분해야 합니다.

실전 빈출 유형 분석: 랜선 자르기 vs 입국심사

매개 변수 탐색의 정석으로 통하는 두 가지 결을 비교해 보겠습니다. 이 두 가지 구조만 완벽하게 장악하면 웬만한 변형 문제는 응용 가능합니다.

비교 요소	랜선 자르기 유형 (최댓값 찾기)	입국심사 유형 (최솟값 찾기)
mid의 의미	자르고자 하는 랜선의 길이 (L)	모든 사람이 심사를 받는 데 드는 총 시간 (T)
결정 함수 내부	각 랜선을 L로 나눈 몫의 총합을 구함	T 시간 동안 각 심사관이 처리할 수 있는 인원의 총합을 구함
참(true)일 때 이동	원하는 개수 이상 나왔으므로, 더 길게 자를 수 있는지 확인 \rightarrow left = mid + 1	목표 인원 이상 처리했으므로, 시간을 더 줄일 수 있는지 확인 \rightarrow right = mid - 1
right 초기값 설정	입력으로 주어진 랜선 중 가장 긴 길이	가장 느린 심사관의 시간 \times 대기 인원 (최악의 시나리오)

여기서 실무적(혹은 시험적)으로 가장 중요한 포인트는 자료형 오버플로우입니다. 입국심사 유형처럼 '시간 \times 인원'을 계산하는 순간 32비트 정수형(int) 범위를 가볍게 넘어서는 경우가 허다합니다. 자바 기준으로 left, right, mid, 그리고 결정 함수 내부의 합산 변수까지 전부 long 타입으로 박고 시작하는 게 정신 건강에 좋습니다. 형변환 실수 하나로 0점 처리되면 억울해서 잠 안 옵니다.

결국 어떤 선택을 해야 하는가?

이분탐색 문제풀이의 핵심 능력을 요약하자면 복잡한 문제 조건 속에서 "결정 함수(isValid)를 얼마나 빠르고 깔끔하게 O(N) 수준으로 구현해내느냐"로 수렴됩니다. 전체 시간 복잡도가 $O(N \log M)$이 되기 때문에, 결정 함수 내부가 무거워지면 이분탐색을 아무리 잘 짜도 시간 초과가 납니다.

시험장에서 막혔을 때는 다음 두 가지만 조율하십시오.

• 데이터 범위가 무지막지한가? \rightarrow 정답을 하나 찍어두고 참/거짓을 판별하는 '매개 변수 탐색' 템플릿을 소환한다.
• 경계선에서 정답이 한 칸씩 밀리는가? \rightarrow 조건이 맞을 때 무조건 ans = mid로 값을 고정해두고 범위를 한 칸 밖으로 밀어버리는 무한 루프 방지 템플릿을 적용한다.

이 구조만 손에 익히면, 어떤 변형 문제가 나와도 정답의 범위를 쪼개 들어가는 묵직한 감각을 유지할 수 있을 것입니다. 실전 코테에서 흔들리지 않는 로직을 짜길 바랍니다.

 

코딩테스트 문자열 인덱스 실수(Out of Bounds) 줄이는 4가지 방어적 코드 패턴