이분 탐색은 어떤 알고리즘인가?
이분 탐색은 배열에서 탐색 범위를 절반으로 줄여나가며 원하는 타겟을 효율적으로 찾는 알고리즘이다.
보통 시작 인덱스와 끝 인덱스 범위를 미리 설정해두고, 가운데 인덱스를 구해 타겟보다 큰 지/작은 지에 따라 탐색 범위를 조정해나간다.
대소 비교로 범위를 정하기 때문에 기본적으로 데이터가 정렬되어 있어야 한다.
일반적으로 배열을 모두 순회하며 값을 찾으려면 O(N)의 시간복잡도를 가지지만, 이분 탐색은 탐색 범위가 절반씩 줄어드므로 O(logN)의 시간복잡도를 가진다.
이분 탐색은 언제 쓰이는가?
- 문제가
단조성(일방향적인 변화)을 띌 때
쉽게 말하면 어떤 값이 커지거나 작아질수록 결과가 한 방향으로만 변하는 성질을 말한다.
아래처럼 중간에 뒤집히는 지점이하나만존재하는 케이스를 말한다.
NO NO NO | YES YES YES
YES YES YES | NO NO NO- 특정 값의 위치를 찾거나 어디에 값을 넣어야 할 지 찾아야 할 때
- 모든 값을 하나씩 순회하면(brute force) 시간 초과가 발생할 때
이분 탐색은 어떻게 구현할 수 있는가?
- 양끝 범위를 지정한다.
- 양끝 범위를 이용해 가운데 값을 구한다.
- 가운데 값을 타겟 값과 비교한다.
가운데 값 === 타겟 값이면 위치 반환가운데 값 > 타겟 값이면 더 높은 범위에서 값을 찾기 위해 시작 인덱스 = 중간 인덱스 + 1로 설정하고 재탐색가운데 값 < 타겟 값이면 더 낮은 범위에서 값을 찾기 위해 끝 인덱스 = 중간 인덱스 - 1로 설정하고 재탐색
반복문/재귀로 구현하는 두 가지 방법이 있지만 재귀는 함수 호출이 누적되어 스택 오버플로우가 발생할 수 있으므로 반복문으로 구현하는 것이 더 효율적이다.
function BinarySearch(arr, target){
let start = 0;
let end = arr.length - 1;
let mid;
while(start <= end){
mid = Math.floor((start + end) / 2);
if(arr[mid] === target) return mid;
else if(arr[mid] < target) start = mid + 1;
else if(arr[mid] > target) end = mid - 1;
}
return -1;
}관련 문제 풀어보기
[백준] 공유기 설치
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/2110
이분 탐색을 어떻게 써야 할 지 감이 안 잡혀서 힌트를 봤다.
공유기 사이 거리가 최대가 되도록 하는 거리 값을 구해야 하므로 거리를 이분 탐색으로 구해야 한다.
공유기를 어떻게 배치하지? (x) -> 특정 거리에서 공유기 배치가 가능한가? (o)
- 우선 이분 탐색을 하려면 배열이 정렬되어 있어야 하므로 주어진 인풋을 오름차순으로 정렬한다.
- 이후 최소 거리를 1, 최대 거리를 배열 양끝 값의 차로 설정한다.
- 배열을 순회하며 설정한 거리값(중간값)으로 몇 개의 집에 공유기를 설치할 수 있는지 카운트한다.
- 카운트 개수가 주어진 공유기의 개수보다 같거나 크면 설정한 중간값으로 설치가 가능한 것이므로 더 큰 범위에서도 설치가 가능한지 확인하기 위해 start = mid + 1로 설정해 재탐색한다.
- 카운트 개수가 주어진 공유기의 개수보다 작으면 설치가 불가능한 것이므로 더 작은 범위에서 탐색하기 위해 end = mid - 1로 설정해 재탐색한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N, C] = input.shift().split(' ').map(Number)
const houseArr = input.map(Number).sort((a,b) => a-b);
let answer = 0;
function BinarySearch(arr){
let start = 1;
let end = arr[arr.length - 1] - arr[0];
let mid;
while(start <= end){
mid = Math.floor((start + end) / 2);
let cnt = 1;
let last = 0;
for(let i=1;i<N;i++){
if(arr[i] - arr[last] >= mid){
cnt++
last = i
}
}
if(cnt >= C){
answer = mid;
start = mid + 1;
}else{
end = mid - 1;
}
}
console.log(answer)
}
BinarySearch(houseArr)[백준] 기타 레슨
- 난이도 : 골드 5
- 문제 링크 : https://www.acmicpc.net/problem/2343
위의 문제와 유사한 문제로, 블루레이의 최소 크기와 최대 크기를 정해두고 중간값을 이용해 M개 이상 볼 수 있는지에 따라 블루레이 크기를 조정해주면 된다.
처음 풀이에서는 두 가지 원인으로 틀렸다.
- 시간 배열을 오름차순으로 정렬함
문제에서주어진 순서대로녹화해야 한다고 했으므로 순서를 바꾸면 안 된다.
꼭 배열이 정렬되어 있어야만 가능한게 아니라 범위를 절반으로 나누어 탐색하는 것이 포인트이기 때문에 문제가 단조성을 띄는지 확인하는 것이 중요하다. - 시작/끝 범위 설정 오류
최솟값을 1, 최댓값을 100000으로 했는데, 최솟값은 블루레이의 개수가 강의 수와 일치할 때 가장 큰 시간이 되어야 하고, 최댓값은 블루레이 개수가 1개일 때 모든 시간의 합이 되어야 한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N,M]= input[0].split(' ').map(Number);
const times = input[1].split(' ').map(Number); // 강의 순서가 바뀌면 안 되므로 정렬하면 안 됨!
let answer = 0;
function BinarySearch(arr){
let start = Math.max(...arr); // M이 N개일 때 : 가장 큰 시간
let end = arr.reduce((acc,cur) => acc+cur); // M이 1개일 때 : 모든 시간 합
let mid;
while(start <= end){
mid = Math.floor((start + end) / 2);
let cnt = 1;
let sum = 0;
for(let i=0;i<N;i++){
if(sum + arr[i] <= mid){
sum += arr[i]
}else{
sum = arr[i]
cnt++
}
}
if(cnt <= M){
answer = mid;
end = mid - 1;
}else{
start = mid + 1;
}
}
console.log(answer)
}
BinarySearch(times);[백준] 게임
- 난이도 : 실버 3
- 문제 링크 : https://www.acmicpc.net/problem/1072
게임을 몇 번 이겨야 승률이 바뀌는지 반환하면 된다.
앞으로 게임은 항상 이기므로 승률은 그대로거나 증가하는 경우밖에 없다.
따라서 승률을 조정하며 승률이 커지면 횟수를 더 줄여보고, 승률이 그대로면 횟수를 더 증가시키며 답을 찾으면 된다.
처음 문제를 풀 때는 end 범위를 잘못 정해서 틀렸다.
가능한 게임 상한선이 사실상 정해져 있지 않아서 가능한 큰 값(10억)으로 설정해야 한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [X,Y]= input[0].split(' ').map(Number);
const winningRate = Math.floor(Y * 100 / X);
let answer = -1;
function BinarySearch(){
let start = 1;
let end = 1000000000;
while(start <= end){
let mid = Math.floor((start + end) / 2);
if(Math.floor((100 * (Y + mid)) / (X + mid)) > winningRate){
answer = mid;
end = mid - 1;
}else{
start = mid + 1;
}
}
console.log(answer);
}
BinarySearch();공통적으로 시작/끝 범위 설정 때문에 계속 틀려서 범위를 잘 정하는게 가장 중요할 것 같다.
[백준] 먹을 것인가 먹힐 것인가
- 난이도 : 실버 3
- 문제 링크 : https://www.acmicpc.net/problem/7795
값이 중복되는 경우도 있을 수 있어서 단순히 mid 인덱스를 바로 반환하면 틀리게 된다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
let T = +input[0];
let idx = 1;
const answer = [];
while(T > 0){
const [N, M] = input[idx++].split(' ').map(Number);
const A = input[idx++].split(' ').map(Number);
const B = input[idx++].split(' ').map(Number).sort((a,b) => a-b);
let cnt = 0;
for(let i=0;i<A.length;i++){
const v = BinarySearch(A[i],B);
cnt += v;
}
answer.push(cnt)
T--;
}
function BinarySearch(target, arr){
let start = 0;
let end = arr.length;
let mid;
while(start <= end){
mid = Math.floor((start + end) / 2);
if(arr[mid] === target){
break;
}else if(arr[mid] < target){
start = mid + 1;
}else{
end = mid - 1;
}
}
return mid;
}
console.log(answer.join('\n'));타겟이 같거나 작을 때는 end를 mid로 설정해서 범위를 넘지 않게 하면 start가 가능한 개수가 된다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
let T = +input[0];
let idx = 1;
const answer = [];
while(T > 0){
const [N, M] = input[idx++].split(' ').map(Number);
const A = input[idx++].split(' ').map(Number);
const B = input[idx++].split(' ').map(Number).sort((a,b) => a-b);
let cnt = 0;
for(let i=0;i<A.length;i++){
const v = BinarySearch(A[i],B);
cnt += v;
}
answer.push(cnt)
T--;
}
function BinarySearch(target, arr){
let start = 0;
let end = arr.length;
while(start < end){
let mid = Math.floor((start + end) / 2);
if(arr[mid] < target){
start = mid + 1;
}else{
end = mid;
}
}
return start;
}
console.log(answer.join('\n'));
모든게 새롭고 재밌는 프론트엔드 새싹