10주차
이진 탐색은 정렬된 데이터에서 원하는 값이나 조건을 찾을 때, 탐색 범위를 절반씩 줄여가며 확인하는 알고리즘입니다.
처음부터 끝까지 하나씩 확인하는 선형 탐색과 달리, 이진 탐색은 매번 가운데 값을 기준으로 판단합니다.
찾는 값이 가운데 값보다 작다 → 왼쪽 절반 탐색
찾는 값이 가운데 값보다 크다 → 오른쪽 절반 탐색
찾는 값이 가운데 값과 같다 → 탐색 성공
즉 한 번 비교할 때마다 확인해야 하는 범위가 거의 절반으로 줄어들기 때문에 데이터가 많을수록 효율이 좋아집니다.
예를 들어 데이터가 1,000,000개 있다고 생각해봅시다.
선형 탐색은 최악의 경우 1,000,000개를 전부 확인해야 합니다.
하지만 이진 탐색은 탐색 범위를 계속 절반으로 줄이기 때문에 대략 20번 정도의 비교만으로도 값을 찾을 수 있습니다.
1,000,000
→ 500,000
→ 250,000
→ 125,000
→ ...
→ 1
그래서 코딩테스트에서 입력 크기가 매우 크고, 탐색해야 하는 값이나 조건이 일정한 방향성을 가진다면 이진 탐색을 의심해볼 수 있습니다.
이진 탐색에서 가장 중요한 조건은 데이터가 정렬되어 있어야 하는 것 입니다.
오름차순 정렬된 배열이라면 가운데 값과 target을 비교해서 왼쪽으로 갈지 오른쪽으로 갈지 결정할 수 있습니다.
하지만 정렬되어 있지 않은 배열에서는 가운데 값을 기준으로 어느 쪽을 버려야 할지 판단할 수 없습니다.
따라서 일반적인 이진 탐색은 반드시 정렬된 배열에서 사용해야 합니다.
정렬 X → 이진 탐색 사용 불가
정렬 O → 이진 탐색 사용 가능
또한 정답이 될 수 있는 범위를 정해두고 조건을 만족하는지 검사하면서 답을 찾는 방식을 보통 파라메트릭 서치라고 합니다.
이진 탐색에서는 보통 세 개의 값을 사용합니다.
left : 현재 탐색 범위의 왼쪽 끝
right : 현재 탐색 범위의 오른쪽 끝
mid : 현재 탐색 범위의 가운데
가운데 위치는 보통 다음과 같이 구합니다.
int mid = left + (right - left) / 2;
단순히 (left + right) / 2로 구할 수도 있지만, Java나 C++처럼 정수 범위가 정해져 있는 언어에서는 left + right가 너무 커질 경우 오버플로우가 발생할 수 있습니다.
그래서 안전하게 작성하려면
mid = left + (right - left) / 2
같은 방식을 권장합니다.
정렬된 데이터에서 70을 찾는다고 가정한다면
- 가운데 값 확인 (50)
- 찾는 값 70 > 50 이므로 오른쪽 구간으로 이동
- 오른쪽 구간의 가운데 값 확인 (80)
- 찾는 값 70 < 80 이므로 왼쪽 구간으로 이동
- 남은 구간의 가운데 값 확인 (70)
- 찾는 값과 일치하므로 탐색 종료
- 데이터 반환
순서로 진행됩니다.
👍 장점
탐색 속도가 빠릅니다.
시간 복잡도가 O(log N)이기 때문에 데이터가 많아도 효율적으로 탐색할 수 있습니다.
정렬된 데이터와 함께 사용하면 특정 값의 존재 여부, 위치, 개수 등을 빠르게 찾을 수 있습니다.
또한 단순히 값을 찾는 문제뿐 아니라 조건을 만족하는 최소값이나 최대값을 찾는 문제에도 활용할 수 있습니다.
👎 단점
정렬되지 않은 데이터에는 바로 사용할 수 없습니다.
정렬이 필요하다면 정렬 비용 O(N log N)이 추가됩니다.
중복 값이 있는 경우 단순 이진 탐색만으로는 첫 번째 위치나 마지막 위치를 정확히 찾기 어렵습니다.
left, right, mid 갱신을 잘못하면 무한 루프가 발생하거나 정답을 놓칠 수 있습니다.
가장 기본적인 이진 탐색 유형입니다.
특정 값이 배열에 존재하는가
특정 값의 인덱스는 어디인가
여러 개의 query에 대해 값 존재 여부를 판단하라
포인트
배열이 정렬되어 있어야 합니다.
정렬되어 있지 않다면 먼저 정렬해야 합니다.
단 정렬하면 원래 인덱스 정보가 바뀔 수 있으므로 원래 위치가 필요한 문제라면 값과 인덱스를 함께 저장해야 합니다.
중복된 값이 여러 개 있을 때 단순 이진 탐색으로는 target 하나의 위치만 찾을 수 있습니다.
이때는 lower bound와 upper bound를 사용합니다.
정렬된 배열에서 특정 숫자가 몇 번 등장하는가
특정 범위에 속하는 원소가 몇 개인가
target 이상, target 이하의 개수를 구하라
포인트
target의 개수 = upper_bound(target) - lower_bound(target)
범위 개수도 비슷하게 계산할 수 있습니다.
[L, R] 범위의 개수
= upper_bound(R) - lower_bound(L)
정렬 상태를 유지하면서 target을 넣을 위치를 찾는 문제입니다.
target을 넣을 수 있는 가장 왼쪽 위치
target보다 크거나 같은 첫 번째 위치
target보다 큰 첫 번째 위치
포인트
이 유형은 대부분 lower bound 또는 upper bound로 해결할 수 있습니다.
배열에서 특정 값을 찾는 것이 아니라, 가능한 값 중 가장 작은 값을 찾는 문제입니다.
최소 시간 구하기
최소 비용 구하기
최소 길이 구하기
조건을 만족하는 가장 작은 값 구하기
포인트
결과가 다음처럼 가능 가능 가능 불가능 불가능 불가능 으로 나뉘는지 확인합니다.
가장 처음으로 가능이 되는 위치를 찾으면 됩니다.
프로그래머스의 입국심사 문제입니다
https://school.programmers.co.kr/learn/courses/30/lessons/43238
입국심사를 기다리는 사람 수 n과 각 심사관이 한 명을 심사하는 데 걸리는 시간 배열 times가 주어졌을 때 모든 사람이 심사를 끝내는 데 필요한 최소 시간을 구하는 문제입니다. 제한사항은 사람 수 n이 최대 1,000,000,000, 각 심사 시간이 최대 1,000,000,000, 심사관 수가 최대 100,000까지 가능하고 공식 예시 입력은 n = 6, times = [7, 10], 정답은 28입니다.
n = 6
times = [7, 10]
return = 28
이 문제는 정답이 될 수 있는 시간 범위를 이진 탐색합니다.
mid분이 주어졌을 때, n명을 모두 심사할 수 있는가?
예를 들어 mid = 30이라면 다음과 같이 계산할 수 있습니다.
7분 걸리는 심사관 → 30 / 7 = 4명 처리 가능 10분 걸리는 심사관 → 30 / 10 = 3명 처리 가능
총 7명 처리 가능
n = 6명 이상 처리할 수 있으므로 30분은 충분합니다.
하지만 문제에서 원하는 것은 가능한 시간 중 최소 시간입니다.
따라서 30분보다 더 작은 시간도 가능한지 확인해야 합니다.
처리 가능 인원 >= n
→ 시간이 충분함
→ answer 갱신
→ 더 작은 시간을 탐색
처리 가능 인원 < n
→ 시간이 부족함
→ 더 큰 시간을 탐색
이 문제의 가능 여부는 다음과 같은 형태로 나뉩니다.
불가능 불가능 불가능 가능 가능 가능
따라서 가장 처음으로 가능이 되는 시간을 찾으면 됩니다.
class Solution {
public long solution(int n, int[] times) {
long left = 1;
long right = 0;
// 가장 오래 걸리는 심사관에게 n명이 모두 심사받는 경우를 최대 시간으로 설정
for (int time : times) {
right = Math.max(right, time);
}
right *= n;
long answer = right;
while (left <= right) {
long mid = left + (right - left) / 2;
long count = 0;
// mid분 동안 처리 가능한 사람 수 계산
for (int time : times) {
count += mid / time;
// n명 이상 처리 가능하면 더 계산할 필요 없음
if (count >= n) {
break;
}
}
if (count >= n) {
// mid분 안에 모두 처리 가능
// 더 짧은 시간도 가능한지 왼쪽 탐색
answer = mid;
right = mid - 1;
} else {
// mid분으로는 부족함
// 더 긴 시간이 필요하므로 오른쪽 탐색
left = mid + 1;
}
}
return answer;
}
}def solution(n, times):
left = 1
right = max(times) * n
answer = right
while left <= right:
mid = left + (right - left) // 2
count = 0
# mid분 동안 처리 가능한 사람 수 계산
for time in times:
count += mid // time
# n명 이상 처리 가능하면 더 계산할 필요 없음
if count >= n:
break
if count >= n:
# mid분 안에 모두 처리 가능
# 더 짧은 시간도 가능한지 확인
answer = mid
right = mid - 1
else:
# mid분으로는 부족함
# 더 긴 시간이 필요함
left = mid + 1
return answerfunction solution(n, times) {
const target = BigInt(n);
const timesBig = times.map(BigInt);
let left = 1n;
let right = timesBig.reduce((max, time) => {
return time > max ? time : max;
}, 0n) * target;
let answer = right;
while (left <= right) {
const mid = (left + right) / 2n;
let count = 0n;
// mid분 동안 처리 가능한 사람 수 계산
for (const time of timesBig) {
count += mid / time;
// n명 이상 처리 가능하면 더 계산할 필요 없음
if (count >= target) {
break;
}
}
if (count >= target) {
// mid분 안에 모두 처리 가능
// 더 짧은 시간도 가능한지 확인
answer = mid;
right = mid - 1n;
} else {
// mid분으로는 부족함
// 더 긴 시간이 필요함
left = mid + 1n;
}
}
return answer;
}이진 탐색에서 가장 흔한 실수는 정렬 여부나 조건의 단조성을 확인하지 않고 적용하는 것
left와 right를 갱신할 때 이미 확인한 mid를 제외하지 않아 무한 루프가 생기는 것,
while (left <= right) 방식과 while (left < right) 방식을 섞어 쓰는 것을 주의해야 합니다.
또한 중복 값이 있는 배열에서는 일반 이진 탐색이 아무 위치나 반환할 수 있으므로
첫 위치, 마지막 위치, 개수를 구해야 할 때는 lower bound와 upper bound를 사용해야 합니다.
파라메트릭 서치 문제에서는 possible(mid)가 false → true 형태인지 true → false 형태인지 먼저 파악해야 하며,
정답 범위가 큰 문제에서는 Java의 int 대신 long, JavaScript의 Number 대신 BigInt처럼 큰 수를 안전하게 다룰 수 있는 타입을 고려해야 합니다.