- 빈말로라도 알고리즘 문제를 잘 풀진 못하지만(...) 특히나 잘 접하지 않았던 유형의 문제들을 풀어보고자 과거에 풀었던 문제들을 돌아보던 중, 이분 탐색 문제를 엄청나게 안 풀어봤다는 것을 깨달았다.
- 개념적으로는 이분 탐색이 어떤 것인지 알고 있지만, 알고리즘 문제 풀이에 대해서는 확실히 익숙하지 않다는 느낌이 들어, 이분 탐색 문제를 풀고 문제 유형에 익숙해지고자 글을 남기기로 했다.
이분 탐색 문제
- 이분 탐색 형식의 풀이를 요구하는 알고리즘 문제들은 주로 방대한 범위의 수에서 특정 조건을 만족하는 값을 찾는 문제에서 많이 쓰이는 듯 하다.
- 이분 탐색의 이론은, 정렬된 배열 혹은 리스트 내에서 탐색 범위(인덱스)를 절반으로 나누어 가며 탐색 대상의 범위를 좁혀나가는 것이다.
- 이를 알고리즘 문제 풀이에 대입하면, 인덱스가 아닌 실제 찾고자 하는 값을 나누어 가며 찾는 방식으로 푸는 것 같다.
문제 풀이
- 이분 탐색에 익숙해지기 위해 풀었던 몇 가지 문제들의 풀이를 기록한다.
백준 1654 랜선 자르기 & 2805 나무 자르기
서로 다른 문제이나 푸는 방식이 거의 똑같았기 때문에 같이 기록한다.
초반에 언급했던대로, '구하고자 하는 값'을 범위를 나누어 가며 푼다는 느낌으로 풀이한다.
- 랜선 자르기 문제의 경우에는 주어진 랜선들에서 잘라낸 N개를 만들 수 있는 랜선의 최대 길이 이다.
- 나무 자르기 문제의 경우에는 주어진 나무들을 잘라내 총 M미터를 만들 수 있는 절단기의 최대 높이 이다.
이분 탐색의 범위가 나타낼 값을 설정했다면, 탐색을 시작할 시작 값과 끝 값을 정해야 한다. 이 문제들에서 구하고자 하는 값은 주어진 데이터(랜선들의 길이, 나무들의 높이)의 최대값보다 클 수 없으므로, 주어진 데이터 리스트를 오름차순으로 정렬한 후 가장 큰 값을 end 값으로 설정해주었다.
필요한 모든 값들을 설정해주었다면, 남은 것은 이분 탐색을 따라 탐색 범위를 절반으로 나누며 조건을 만족하는 값을 찾는 것이다. 아래의 코드는 1654번 랜선 자르기 문제를 기준으로 짜인 코드이다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on("line", (line) => {
input.push(line);
}).on("close", function () {
const [k, n] = input
.shift()
.split(" ")
.map((el) => parseInt(el));
const inputArr = input.map((el) => parseInt(el)).sort((a, b) => a - b);
let answer = -Infinity;
let start = 1, end = inputArr[inputArr.length - 1];
while (start <= end) {
const mid = Math.floor((start + end) / 2);
const divided = inputArr
.map((el) => Math.floor(el / mid))
.reduce((acc, cur) => {
acc += cur;
return acc;
}, 0);
if (divided >= n) {
answer = Math.max(answer, mid);
start = mid + 1;
} else if (divided < n) {
end = mid - 1;
}
}
console.log(answer);
process.exit();
});
백준 2343 기타 레슨
이분 탐색을 진행할 때 탐색 범위를 어떻게 지정해야 할지 등에 대해 고민하게 하는 동시에, 약간의 편견(?)에서 벗어나게 해준 문제.
각 강의의 시간이 주어지면, 이 강의들을 M개의 블루레이 내에 모두 녹화할 수 있게 하는 각 블루레이 크기의 최소값을 구해야 한다. 여담으로 지문 내에 '블루레이의 개수를 가급적 줄이려고 한다' 라는 서술이 있으므로, 실은 M개 보다 더 적은 수의 블루레이를 써도 괜찮다. 따라서 구해야 하는 값은 각 블루레이가 가질 수 있는 최소값의 크기이므로, 이것을 탐색 대상인 중간값으로 설정한다.
이분 탐색 문제를 풀 경우, 이분 탐색의 조건인 '이미 정렬된 배열을 대상으로 한다'라는 전제에 사로잡힌 나머지 어떤 문제든 일단 풀 때마다 데이터 리스트를 오름차순으로 정렬부터 하곤 했는데, 이 문제는 그러면 안 된다. 왜냐하면 '강의의 순서가 지켜져야 한다'는 규칙이 있기 때문이다.
탐색 범위의 경우, 최소값은 쉽게 1로 정할 수 있었지만 최대값을 어떻게 설정해야 할지 고민을 잠깐 했었는데, 문제의 조건으로 '각 강의의 길이는 10,000분을 넘지 않는다'고 나왔으므로 N개의 강의가 최대 크기(10,000분)일 때 이들을 하나의 블루레이에 모두 녹화할 수 있는 (N * 10,000)을 최대값으로 잡았다.
여기까지 결정했으면 남은 작업은 위의 문제와 유사하다. 탐색 범위를 절반씩 줄여가며 모든 강의를 M개 이하의 블루레이를 사용해 녹화할 수 있는 블루레이 크기의 최소값을 구하면 된다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on("line", (line) => {
input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
const [n, m] = input.shift();
const arr = input.shift();
let start = 1, end = n * 10000;
let answer = Infinity;
// M개 이하의 블루레이에 주어진 용량으로 모든 강의를 녹화할 수 있는지 확인한다
const checkBluerayCapacity = (capacity) => {
let currentCap = 0, totalBlueray = 0;
for (let i = 0; i < n; i++) {
if (capacity < arr[i]) {
return false;
}
if (currentCap + arr[i] > capacity) {
totalBlueray++;
currentCap = 0;
}
currentCap += arr[i];
if (totalBlueray > m) break;
}
totalBlueray += 1;
if (totalBlueray <= m) return true;
else return false;
};
while (start <= end) {
const mid = Math.floor((start + end) / 2);
if (checkBluerayCapacity(mid)) {
answer = Math.min(answer, mid);
end = mid - 1;
} else {
start = mid + 1;
}
}
console.log(answer);
process.exit();
});
백준 2110 공유기 설치
위 문제들과 비슷한 유형이지만, 아이디어를 도출하는데 약간 애먹은 문제. 수직선 상에 위치한 N개의 집들의 좌표가 주어지면 이 집들에 C개의 공유기를 설치하고 최종적으로 가장 인접한 두 공유기 사이 거리의 최대값을 구하는 문제이다.
맞는지 아닌지의 여부를 차치하고 2개의 아이디어가 나왔다. 하나는 주어진 집의 좌표들을 오름차순으로 정렬한 후 진행하는 것, 다른 하나는 집 좌표들을 오름차순으로 정렬한 후 각 집 사이의 거리 차이를 구한 배열을 만들어 진행하는 것이었는데, 전자로 풀었지만 후자로 했어도 딱히 달라지는 것은 없었을 것 같다. 결국에는 집 사이 거리를 구하면서 진행해야 했기 때문이다.
풀이 과정은 아래와 같다.
- 이분 탐색의 목표값을 '가장 인접한 두 공유기 사이의 거리의 최소값'으로 설정, 탐색의 범위 또한 이에 맞게 두 집 사이의 거리로 가능한 값 중 가장 작은 값과 가장 큰 값을 선정한다.
- 두 집 사이 거리로 가능한 가장 작은 값은 1, 가장 큰 값은 주어진 집 좌표를 오름차순으로 정렬했을 때 첫 번째 값을 마지막 값에서 뺀 값이 된다(코드 참고).
- 범위를 정했다면 해당 범위를 가지고 탐색을 시작한다. 구한 중간값이 문제의 조건에 해당하는지 확인하기 위해, 좌표 배열을 돌며 각 집 사이의 거리를 구하고, 이 거리가 중간값보다 크거나 같은 거리의 개수를 센다.
- 이렇게 센 개수가 공유기의 개수(C)보다 크거나 같다면 문제의 조건을 만족하는 경우이므로 해당 답을 기록한다.
- 이 때, 공유기 개수와 정확히 맞을 때가 아니라 공유기 개수보다 더 많을 때도 포함시켜야 한다. 공유기 개수보다 많을 경우 그 중 C개 만큼을 선택해서 문제의 조건을 만족시킬 수 있다는 의미이기 때문이다.
위의 로직을 코드로 작성한 것이 아래와 같다.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on("line", (line) => {
input.push(line);
}).on("close", function () {
const [n, c] = input.shift().split(' ').map(el => parseInt(el));
const inputArr = input.map(el => parseInt(el)).sort((a, b) => a - b);
if (c === 2) {
console.log(inputArr[inputArr.length - 1] - inputArr[0]);
process.exit();
}
if (c === n) {
let min = Infinity;
for (let i = 0; i < n - 1; i++) {
min = Math.min(inputArr[i + 1] - inputArr[i]);
}
console.log(min);
process.exit();
}
let answer = -Infinity;
let start = 1, end = inputArr[n - 1] - inputArr[0];
const checkIsPossible = (distance) => {
let count = 1;
let prev = inputArr[0];
for (let i = 1; i < n; i++) {
if (inputArr[i] - prev >= distance) {
count++;
prev = inputArr[i];
}
}
return count;
};
while (start <= end) {
const mid = Math.floor((start + end) / 2);
const count = checkIsPossible(mid);
if (count >= c) {
start = mid + 1;
answer = Math.max(answer, mid);
} else {
end = mid - 1;
}
}
console.log(answer);
process.exit();
});- 이래저래 간단한 이분 탐색은 감이 좀 잡히는 듯 한데, 아직 아리까리한 부분도 많은 느낌.
- 늦은 감은 있지만 그래도 이 기회를 통해 이분 탐색 문제를 접해봤으니, 다음부턴 차차 난이도를 높혀가며 심화 유형에 익숙해져야겠다.
'공부 > 알고리즘' 카테고리의 다른 글
| 프로그래머스 단어 변환 풀이 (0) | 2024.11.24 |
|---|---|
| 백준 17837번 새로운 게임 2 풀이 (0) | 2024.11.17 |
| 비트마스킹 간단 정리하기 (0) | 2024.11.11 |
| 외판원 순환 문제 알아보기 (3) | 2024.11.10 |
| 위상 정렬 알아보기 (0) | 2024.08.31 |