이분 탐색(Binary Search) & 매개변수 탐색
이분 탐색이란?
정의: 정렬된 데이터에서 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는 알고리즘
특징: 매번 탐색 범위가 1/2로 감소 → O(log N)의 시간복잡도
핵심: "답의 범위를 좁혀가며 최적값 찾기"
매개변수 탐색이란?
일반적인 문제: "조건을 만족하는 X를 구하시오"
↓ (발상의 전환)
매개변수 탐색: "X가 주어졌을 때 조건을 만족하는가?"
↓ (이분 탐색 적용)
답: 조건을 만족하는 X의 최댓값/최솟값
📌 문제 분석
문제 요약
나무꾼이 나무를 자르는 문제. 절단기 높이 H를 설정하면 H보다 높은 나무들이 잘려요!
상황 설명
• 절단기 높이 H 설정 • H보다 높은 나무의 윗부분만 잘림 • 잘린 나무들을 모두 가져감 • 최소 M미터가 필요
목표
M미터 이상을 얻으면서 H를 최대한 높게 설정
제한사항
• N: 나무의 수 (1 ≤ N ≤ 1,000,000) • M: 필요한 나무 길이 (1 ≤ M ≤ 2,000,000,000) • 각 나무의 높이 (0 ≤ 높이 ≤ 1,000,000,000)
문제 접근 방법
1️⃣ 그림으로 이해하기
나무 높이: [20, 15, 10, 17]
절단기 H = 15
20 15 10 17
|| || || ||
|| || || ||
|| == || || ← H=15 (절단선)
|| || ==
||
[5m] [0m] [0m] [2m] = 총 7m 획득!
2️⃣ 왜 이분 탐색을 사용할까?
❌ 완전탐색 시도
H를 0부터 최대높이까지 하나씩 시도
- 시간복잡도: O(최대높이 × N) = O(10⁹ × 10⁶) = 시간초과!
✅ 이분 탐색 적용
H의 범위를 절반씩 줄여가며 탐색
- 시간복잡도: O(log(최대높이) × N) = O(30 × 10⁶) = 통과!
3️⃣ 이분 탐색 시뮬레이션
나무: [4, 42, 40, 26, 46], M=20 필요
1단계) left=0, right=46, mid=23
→ 잘린 나무: 19+17+3+23=62 ≥ 20 ✓
→ 더 높일 수 있나? left=24
2단계) left=24, right=46, mid=35
→ 잘린 나무: 7+5+11=23 ≥ 20 ✓
→ 더 높일 수 있나? left=36
3단계) left=36, right=46, mid=41
→ 잘린 나무: 1+5=6 < 20 ✗
→ 높이 낮춰야 함! right=40
4단계) left=36, right=40, mid=38
→ 잘린 나무: 4+2+8=14 < 20 ✗
→ 높이 낮춰야 함! right=37
5단계) left=36, right=37, mid=36
→ 잘린 나무: 6+4+10=20 = 20 ✓
→ 더 높일 수 있나? left=37
6단계) left=37, right=37, mid=37
→ 잘린 나무: 5+3+9=17 < 20 ✗
→ 종료!
답: H=36
📝 풀이 코드
JavaScript 코드
// 언어 : Javascript , (성공/실패) : 1/0 , 메모리 : 137416 KB , 시간 : 676 ms
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const [N, M] = input[0].split(" ").map(Number);
const trees = input[1].split(" ").map(Number);
// 이진 탐색 범위 설정
let left = 0; // 최소 높이
let right = Math.max(...trees); // 최대 높이 (가장 높은 나무)
let answer = 0; // 정답 저장
while (left <= right) {
const mid = Math.floor((left + right) / 2);
// mid 높이로 잘랐을 때 얻는 나무 계산
let total = 0;
for (const tree of trees) {
if (tree > mid) {
total += tree - mid;
}
}
// M미터 이상 얻을 수 있는지 확인
if (total >= M) {
answer = mid; // 가능하면 답 갱신
left = mid + 1; // 더 높은 높이 시도
} else {
right = mid - 1; // 높이를 낮춰야 함
}
}
console.log(answer);
🔎 코드 상세 해설
Step 1. 탐색 범위 설정
let left = 0; // 절단기 최소 높이
let right = Math.max(...trees); // 절단기 최대 높이
- 최소: 0 (모든 나무를 다 자르는 경우)
- 최대: 가장 높은 나무의 높이 (아무것도 안 자르는 경우)
Step 2. 중간값으로 시뮬레이션
let total = 0;
for (const tree of trees) {
if (tree > mid) { // mid보다 높은 나무만
total += tree - mid; // 잘린 부분 계산
}
}
- 절단기보다 낮은 나무는 안 잘림 → 0
- 절단기보다 높은 나무만 계산
Step 3. 범위 조정 로직
if (total >= M) { // 충분히 얻었다면
answer = mid; // 현재 높이 저장
left = mid + 1; // 더 높게 시도
} else { // 부족하다면
right = mid - 1; // 더 낮게 시도
}
⚠️ 중요: total >= M일 때도 계속 탐색! (최댓값을 구해야 하므로)
⏱️ 시간복잡도 분석
| 항목 | 복잡도 | 설명 |
| 이분 탐색 횟수 | O(log H) | 약 30번 |
| 각 탐색마다 계산 | O(N) | 1,000,000 |
| 전체 | O(N × log H) | 약 30,000,000 ✅ |
⚠️ 실수하기 쉬운 부분
❌ 자주 하는 실수 TOP 3
1. answer 업데이트 빼먹기
// 잘못된 코드
if (total >= M) {
left = mid + 1; // answer = mid 빼먹음!
}
2. 범위 설정 실수
// 잘못된 코드
let right = 1000000000; // 나무 최대 높이가 아님!
3. 오버플로우 주의
// M이 20억까지 가능 → Number 타입으로 충분 (2^53까지 안전)
이분 탐색 마스터하기
이런 키워드 보면 이분 탐색!
✅ "최댓값/최솟값을 구하시오"
✅ "~이상/이하를 만족하는"
✅ 답의 범위가 정해져 있음
✅ 특정 값으로 O(N) 계산 가능
✅ 완전탐색하면 시간초과
유사 문제 패턴
패턴 1. 입국심사 문제
심사관들이 있고, 각자 심사 시간이 다름
→ "T시간 안에" 모든 사람 심사 가능?
→ T를 이분 탐색!
패턴 2. 예산 문제
각 부서별 요청 예산이 있고, 총 예산 한계
→ "상한액 X로" 예산 분배 가능?
→ X를 이분 탐색!
패턴 3. 징검다리 문제
돌들 사이의 거리
→ "최소 거리 D 이상" 유지하며 제거 가능?
→ D를 이분 탐색!
핵심 정리
- 이분 탐색 = "답을 맞추는 게임"
- 매개변수 탐색 = "조건 만족 여부를 O/X로 판단"
- left, right 범위 설정이 제일 중요!
- answer 변수로 가능한 답을 계속 갱신
실전 꿀팁
| 구분 | 방법 |
| 최댓값 구하기 | if (조건 만족) left = mid + 1 |
| 최솟값 구하기 | if (조건 만족) right = mid - 1 |
| 핵심 | 항상 answer 변수에 가능한 답 저장! |
💭 느낀점
- 처음엔 "높이를 하나씩 다 해봐야 하나?" 했는데 이분 탐색으로 해결!
- 매개변수 탐색이라는 발상의 전환이 신기했음
- 비슷한 패턴의 문제가 많아서 한 번 익혀두면 유용할 듯
'알고리즘 풀이' 카테고리의 다른 글
| 백준 | 18870번 좌표 압축 (JavaScript 풀이) (0) | 2025.10.05 |
|---|---|
| 백준 | Class3 핵심 알고리즘 개념 정리 (2) | 2025.09.20 |
| 백준 | 2606번 바이러스 (JavaScript 풀이) (0) | 2025.09.09 |
| 백준 | 1463번 1로 만들기 (JavaScript 풀이) (0) | 2025.09.06 |
| 백준 | 1003번 피보나치 함수 (JavaScript 풀이) (0) | 2025.09.05 |
