배운 자료구조들을 실전 문제에 어떻게 꺼내 쓸지가 마지막 관문이에요. 이번 장은 코테에서 반복적으로 등장하는 네 가지 핵심 기법과 문제를 읽는 눈을 정리합니다.
n을 보고 허용되는 복잡도를 가늠할 수 있어요.코테 문제는 대부분 입력 크기 n의 범위를 알려줘요. 이 숫자를 보면 어떤 복잡도까지 통과되는지를 거꾸로 추론할 수 있어요. 보통 1초에 약 1억 번 연산이 기준이에요.
완전 탐색(브루트포스, brute force)은 가능한 모든 경우를 하나도 빠짐없이 확인하는 방법이에요. 아이디어가 필요 없어 가장 먼저 떠올릴 수 있고, 정답을 놓칠 일이 없어요. 대신 경우의 수가 많으면 느려요.
function hasPairBrute(arr, target) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) { // 모든 쌍을 확인
if (arr[i] + arr[j] === target) return true;
}
}
return false;
}투 포인터(two pointers)는 양 끝(또는 두 지점)의 포인터를 조건에 따라 안쪽으로 좁혀가며 답을 찾는 기법이에요. 정렬된 배열에서 두 수의 합 같은 문제를 O(n²)에서 O(n)으로 줄여줘요.
function hasPairSorted(arr, target) { // arr는 오름차순 정렬됨
let lo = 0, hi = arr.length - 1;
while (lo < hi) {
const sum = arr[lo] + arr[hi];
if (sum === target) return true;
if (sum < target) lo++; // 합이 작으면 왼쪽을 키운다
else hi--; // 합이 크면 오른쪽을 줄인다
}
return false;
}슬라이딩 윈도우(sliding window)는 연속된 구간(창, window)을 한 칸씩 이동시키며, 빠진 값은 빼고 새 값만 더하는 방식으로 매번 다시 계산하지 않아요. 그래서 O(n)에 구간 합·최댓값 등을 구할 수 있어요.
function maxWindowSum(arr, k) {
let sum = 0;
for (let i = 0; i < k; i++) sum += arr[i]; // 첫 창의 합
let best = sum;
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k]; // 새 값 더하고, 빠진 값 뺀다
best = Math.max(best, sum);
}
return best;
}그리디(greedy, 탐욕법)는 매 순간 지금 가장 좋아 보이는 선택을 하고, 뒤를 되돌아보지 않는 방법이에요. 구현이 단순하고 빠르지만, 지역적 최선이 전체 최선을 보장하지 않을 수 있어요.
function coinCount(coins, amount) { // coins: 내림차순 정렬
let count = 0;
for (const c of coins) {
count += Math.floor(amount / c); // 가능한 만큼 큰 동전부터
amount %= c;
}
return count; // 사용한 동전 개수
}| 상황(원하는 것) | 고르면 좋은 자료구조 | 이유 |
|---|---|---|
| 빠른 조회·존재 확인 | 해시(Map/Set) | 키로 O(1) 접근 |
| 순서대로 저장·인덱스 접근 | 배열 | 인덱스 접근 O(1) |
| LIFO(마지막이 먼저) | 스택 | 되돌리기·괄호 검사 등 |
| FIFO(먼저 온 게 먼저) | 큐 | 대기열·BFS 등 |
| 정렬 상태 유지·범위 탐색 | 트리(BST 등) | 탐색·삽입 O(log n) |