버리는 것은 위험한 결정입니다. 버린 쪽에 답이 있으면 되돌릴 수 없기 때문입니다.
이분탐색의 조건은 정렬이 아니라 단조성입니다
이분탐색(binary search) 을 배울 때는 보통 정렬된 배열에서 값을 찾는 예로 시작합니다. 그래서 정렬이 조건이라고 기억하게 됩니다.
정확히는 단조성(monotonicity) 이 조건입니다. 어떤 지점을 경계로 조건이 한 번만 바뀌면 됩니다. 왼쪽은 전부 거짓이고 오른쪽은 전부 참인 형태입니다.
정렬된 배열에서 값을 찾는 건 이 조건의 특수한 경우입니다. “이 위치의 값이 찾는 값보다 크거나 같은가”라는 질문에 대한 답이 정확히 한 번 거짓에서 참으로 바뀝니다.
이렇게 다시 정의하면 쓸 수 있는 범위가 넓어집니다. 배열이 아니어도, 값을 찾는 게 아니어도 단조성만 있으면 절반을 버릴 수 있습니다.
git bisect가 이 성질을 씁니다. 커밋을 시간 순으로 늘어놓으면 어느 지점부터 버그가 나타나고 그 뒤로는 계속 나타나므로, 판정이 한 번만 뒤집힙니다. 커밋이 천 개여도 열 번 남짓 빌드해보면 처음 깨진 커밋을 찾습니다.
답 자체를 이분탐색합니다
파라메트릭 서치(parametric search) 는 최적값을 직접 계산하는 대신 후보값 하나를 두고 그것이 가능한지 판정하는 문제로 바꾸는 방법으로, 이 확장의 대표적인 형태입니다.
랜선 N개를 잘라 M개의 같은 길이 조각을 만들 때 가능한 최대 길이를 구한다고 해봅시다. 최대 길이를 바로 계산하기는 어렵습니다. 대신 이렇게 묻습니다.
“길이 x로 자르면 M개를 만들 수 있는가”
이 질문에는 답하기 쉽습니다. 각 랜선을 x로 나눈 몫을 다 더해 M 이상인지 보면 됩니다. 그리고 이 질문에는 단조성이 있습니다. x가 작으면 만들 수 있고 어느 지점을 넘으면 만들 수 없어서, 참에서 거짓으로 한 번만 바뀝니다.
경계를 찾으면 그 경계가 답입니다.
function maxLength(cables, m) {
// 판정: 길이 x로 자르면 m개 이상 나오는가
const canMake = (x) =>
cables.reduce((sum, len) => sum + Math.floor(len / x), 0) >= m;
let lo = 1;
let hi = Math.max(...cables);
let answer = 0;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2); // 오버플로 회피 형태
if (canMake(mid)) {
answer = mid; // 가능하면 더 길게 시도
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return answer;
}파라메트릭 서치가 하는 일은 결국 최적화 문제를 판정 문제로 바꾸는 것입니다. 최댓값이나 최솟값을 묻는 문제에서 “이 값이 가능한가”로 바꿔 물었을 때 단조성이 보이면 이 방법을 쓸 수 있습니다.
실무에서도 같은 방식으로 임계값을 정합니다. 목표 응답 시간을 지키는 최소 워커 수나, 메모리 한도를 넘지 않는 최대 배치 크기가 그런 값입니다. 워커를 늘리면 응답 시간이 줄어들기만 하므로 판정에 단조성이 있고, 후보를 하나씩 넣어 부하 테스트를 돌리는 대신 절반씩 좁힐 수 있습니다.
경계 조건을 매번 틀리지 않으려면
이분탐색에서 시간을 가장 많이 잡아먹는 것은 경계 처리입니다. lo <= hi인지 lo < hi인지, mid + 1인지 mid인지가 매번 헷갈립니다.
외우는 대신 형태를 하나로 고정하는 편이 낫습니다. 조건을 만족하는 첫 위치를 찾는 형태만 쓰면 대부분의 변형을 여기서 파생시킬 수 있습니다.
// 조건을 만족하는 첫 인덱스를 찾는다. 없으면 arr.length
function lowerBound(arr, predicate) {
let lo = 0;
let hi = arr.length; // 닫히지 않은 구간
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (predicate(arr[mid])) hi = mid; // 조건 만족: 자기 자신도 후보
else lo = mid + 1; // 불만족: 자기 자신은 제외
}
return lo;
}
const arr = [1, 3, 3, 5, 7];
lowerBound(arr, (v) => v >= 3); // 1
lowerBound(arr, (v) => v > 3); // 3hi를 배열 길이로 두고 반열린 구간을 쓰면 조건이 하나로 정리됩니다. 값 하나를 찾는 것도, 삽입 위치를 찾는 것도, 개수를 세는 것도 lowerBound 하나의 조합으로 나옵니다.
투 포인터는 두 방향에서 좁힙니다
정렬된 배열에서 합이 특정 값이 되는 두 원소를 찾는 문제를 생각해봅니다. 모든 쌍을 확인하면 O(N²)입니다.
투 포인터(two pointers) 로 양 끝에서 시작하는 포인터 두 개를 쓰면 O(N)이 됩니다. 합이 목표보다 크면 오른쪽 포인터를 왼쪽으로, 작으면 왼쪽 포인터를 오른쪽으로 옮깁니다.
function findPair(sorted, target) {
let left = 0;
let right = sorted.length - 1;
while (left < right) {
const sum = sorted[left] + sorted[right];
if (sum === target) return [left, right];
if (sum > target) right--; // 합을 줄여야 한다
else left++; // 합을 늘려야 한다
}
return null;
}여기서도 근거는 단조성입니다. 배열이 정렬되어 있으므로 오른쪽 포인터를 왼쪽으로 옮기면 합이 반드시 줄어듭니다. 방향이 확실하니 되돌아갈 이유가 없습니다.
슬라이딩 윈도우(sliding window) 는 같은 아이디어를 구간에 적용한 형태입니다. 조건을 만족하는 동안 오른쪽 끝을 늘리고, 어기면 왼쪽 끝을 당깁니다. 각 포인터가 배열을 한 번씩만 통과하므로 전체가 O(N)입니다.
레이트 리미터가 이 형태로 동작합니다. 최근 1분 안의 요청만 창에 남기고 앞쪽의 오래된 요청을 버리면, 요청이 들어올 때마다 전체를 다시 세지 않아도 됩니다.
백트래킹은 완전탐색에 가지치기를 더합니다
모든 경우를 나열하되, 도중에 답이 될 수 없다고 판정되면 그 아래를 통째로 버리는 방식이 백트래킹(backtracking) 입니다.
N개의 퀸을 서로 공격하지 않게 놓는 문제에서, 두 번째 줄까지 놓았는데 이미 충돌한다면 세 번째 줄부터의 모든 경우를 확인할 이유가 없습니다. 이 가지치기(pruning) 가 성능을 크게 높여줍니다.
function permutations(items) {
const result = [];
const used = new Array(items.length).fill(false);
const path = [];
function backtrack() {
if (path.length === items.length) {
result.push([...path]); // 복사해서 담는다
return;
}
for (let i = 0; i < items.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(items[i]);
backtrack();
path.pop(); // 선택을 되돌린다
used[i] = false;
}
}
backtrack();
return result;
}선택하고, 내려가고, 되돌리는 세 단계로 이루어집니다. 되돌리는 부분을 빠뜨리면 상태가 원래대로 돌아가지 않아 엉뚱한 결과가 나옵니다.
최악 복잡도는 완전탐색과 같습니다. 가지치기는 평균적인 실행 시간을 줄일 뿐 상한을 바꾸지 않습니다.
비트마스킹은 부분집합을 정수로 만듭니다
원소가 20개 이하일 때 모든 부분집합을 다뤄야 한다면, 집합 하나를 정수 하나로 표현할 수 있습니다. 각 비트가 해당 원소의 포함 여부이고, 이렇게 집합을 정수의 비트로 나타내는 기법이 비트마스킹(bitmasking) 입니다.
const n = items.length; // n <= 20
for (let mask = 0; mask < (1 << n); mask++) {
const subset = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) subset.push(items[i]); // i번 비트가 켜져 있으면 포함
}
// subset으로 처리
}집합 연산이 비트 연산으로 바뀝니다. 합집합은 |, 교집합은 &, 특정 원소 추가는 |= (1 << i)입니다. 배열이나 Set을 다루는 것보다 빠르고, 방문 표시를 정수 하나로 관리할 수 있어 상태 공간 탐색에서 특히 유용합니다.
파일 권한이 이 방식으로 저장됩니다. 읽기와 쓰기와 실행을 비트 세 개로 두면 chmod 755 같은 숫자 하나가 권한 전체를 나타내고, 기능 플래그를 켜고 끄는 설정도 같은 방식으로 정수 하나에 담을 수 있습니다.
한계는 명확합니다. 2의 N승이 경우의 수이므로 N이 25를 넘어가면 감당하기 어렵습니다. 2²⁵만 해도 약 3,300만 개입니다. 자바스크립트에서는 비트 연산이 32비트 정수로 처리된다는 점도 고려해야 합니다.
참고 자료
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- MDN Web Docs. 비트 연산자. Mozilla. https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Operators
다음 편 예고
매 순간 가장 좋아 보이는 선택을 이어가면 전체 답이 되는 문제가 있고, 그렇지 않은 문제가 있습니다. 둘을 가르는 조건과, 그리디가 깨질 때 무엇으로 넘어가야 하는지 봅니다.