이번 편의 결과물: coding-test/13-dynamic-programming/에 계단 오르기·최대 연속 부분합·0/1 냅색·최장 증가 부분열 4문제 풀이와 테스트를 작성해 node --test를 통과시킵니다. · 다루는 개념: 메모이제이션, 타뷸레이션, 상태 전이식 세우기
이 편에서 만드는 파일
coding-test/
└── 13-dynamic-programming/
├── 01-climb-stairs/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 02-max-subarray-sum/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 03-knapsack/
│ ├── solution.js (+)
│ └── solution.test.js (+)
└── 04-longest-increasing-subsequence/
├── solution.js (+)
└── solution.test.js (+)개념 정리
메모이제이션과 타뷸레이션
09편의 재귀는 같은 부분 문제를 여러 번 다시 계산하는 경우가 있습니다. 동일한 입력에 대해 항상 같은 결과가 나오는 문제(최적 부분 구조 + 겹치는 부분 문제)라면, 한 번 계산한 값을 저장해 두고 재사용할 수 있습니다.
| 방식 | 계산 방향 | 구현 형태 | 특징 |
|---|---|---|---|
| 메모이제이션 | 위에서 아래로(재귀 + 캐시) | Map 또는 배열에 결과 저장 후 재귀 호출 전에 조회 | 필요한 부분 문제만 계산 |
| 타뷸레이션 | 아래에서 위로(반복문) | 작은 문제부터 배열을 채워 나감 | 재귀 호출 비용·스택 오버플로 없음 |
이번 편은 4문제 모두 타뷸레이션(반복문 + 배열)으로 구현합니다. 재귀 호출 스택 깊이 제한 없이 큰 입력도 안정적으로 처리할 수 있기 때문입니다.
상태 전이식 세우는 절차
DP 문제를 풀 때는 다음 순서로 접근합니다.
- 상태 정의: 배열의 각 칸이 무엇을 의미하는지 정합니다(예:
dp[i]는i번째까지 봤을 때의 최적값). - 점화식(상태 전이식):
dp[i]를 이전 상태들로 표현하는 식을 세웁니다. - 초기값: 더 이상 쪼갤 수 없는 가장 작은 경우의 값을 정합니다.
- 계산 순서: 초기값에서 시작해 점화식대로 배열을 채우는 순서를 정합니다(보통 인덱스가 작은 쪽에서 큰 쪽으로).
아래 4문제 모두 이 절차를 그대로 적용합니다. 상태 정의와 점화식은 문제마다 접근 부분에서 설명합니다.
문제 1. 층계 오르는 방법의 수
문제 설명
한 번에 1칸 또는 2칸씩만 올라갈 수 있는 층계가 있습니다. 층계가 n칸일 때, 맨 아래에서 맨 위까지 올라가는 방법의 수를 구합니다. 순서가 다르면 다른 방법으로 셉니다(1칸+2칸과 2칸+1칸은 다른 방법).
| 제약 | 값 |
|---|---|
n의 범위 | 1 이상 40 이하인 정수 |
입출력 예
입력(n) | 출력 | 설명 |
|---|---|---|
| 2 | 2 | 1+1, 2 |
| 3 | 3 | 1+1+1, 1+2, 2+1 |
| 5 | 8 | 경우의 수가 피보나치 수열과 같은 규칙으로 늘어남 |
접근
dp[i]를 “i칸을 오르는 방법의 수”로 정의합니다. 마지막 걸음이 1칸이면 dp[i-1]가지 방법 뒤에 1칸을 더한 것이고, 마지막 걸음이 2칸이면 dp[i-2]가지 방법 뒤에 2칸을 더한 것이므로 점화식은 dp[i] = dp[i-1] + dp[i-2]입니다. 초기값은 dp[0] = 1(가만히 있는 방법 1가지), dp[1] = 1입니다. 배열 하나를 앞에서부터 채우므로 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.
풀이
// coding-test/13-dynamic-programming/01-climb-stairs/solution.js
// 시간복잡도: O(n) — dp 배열을 앞에서부터 한 번씩 채운다
// 공간복잡도: O(n) — 1칸부터 n칸까지의 경우의 수를 배열에 저장한다
export function solution(n) {
if (n <= 1) return 1;
const ways = [1, 1];
for (let i = 2; i <= n; i++) {
ways[i] = ways[i - 1] + ways[i - 2];
}
return ways[n];
}테스트
// coding-test/13-dynamic-programming/01-climb-stairs/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('n이 2이면 2가지', () => {
assert.strictEqual(solution(2), 2);
});
test('n이 3이면 3가지', () => {
assert.strictEqual(solution(3), 3);
});
test('n이 5이면 8가지', () => {
assert.strictEqual(solution(5), 8);
});
test('n이 0이면 1가지(가만히 있기)', () => {
assert.strictEqual(solution(0), 1);
});node --test coding-test/13-dynamic-programming/01-climb-stairs/solution.test.js함정
- 점화식을
dp[i] = dp[i-1] * dp[i-2]처럼 곱셈으로 착각하기 쉽습니다. “경우의 수를 더한다”는 것을 항상 그림으로 먼저 확인합니다. ways배열을new Array(n)으로만 만들고ways[0],ways[1]초기값을 빠뜨리면NaN이 전파됩니다.
문제 2. 연속 구간 최대 합
문제 설명
정수 배열이 주어질 때, 연속된 부분 배열(길이 1 이상) 중 합이 최대인 값을 구합니다. 배열에는 음수도 포함될 수 있습니다.
| 제약 | 값 |
|---|---|
| 배열 길이 | 1 이상 10만 이하 |
| 원소 범위 | 각각 -1000 이상 1000 이하인 정수 |
입출력 예
| 입력 | 출력 | 설명 |
|---|---|---|
| [-2, 1, -3, 4, -1, 2, 1, -5, 4] | 6 | [4, -1, 2, 1] 구간의 합이 최대 |
| [1] | 1 | 원소가 하나면 그 값이 답 |
| [5, 4, -1, 7, 8] | 23 | 배열 전체를 더한 값이 최대 |
접근
dp[i]를 “i번째 원소로 끝나는 연속 구간의 최대 합”으로 정의합니다. i번째 원소를 포함하는 구간을 만들 때, 이전까지의 최대 합(dp[i-1])이 양수면 이어 붙이는 것이 유리하고, 음수면 i번째 원소부터 새로 시작하는 것이 유리합니다. 점화식은 dp[i] = max(nums[i], dp[i-1] + nums[i])입니다. 이 방식을 카데인 알고리즘(Kadane’s algorithm)이라고 부릅니다. 배열 전체 최댓값은 dp 값들 중 최댓값이며, 변수 하나로 이전 값만 기억하면 되므로 시간 복잡도 O(n), 공간 복잡도 O(1)입니다.
풀이
// coding-test/13-dynamic-programming/02-max-subarray-sum/solution.js
// 시간복잡도: O(n) — 배열을 한 번 순회하며 카데인 알고리즘을 적용한다
// 공간복잡도: O(1) — 변수 두 개만으로 이전 상태를 기억한다
export function solution(nums) {
let best = nums[0];
let current = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
}테스트
// coding-test/13-dynamic-programming/02-max-subarray-sum/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('음수가 섞인 배열에서 최대 부분합을 찾는다', () => {
assert.strictEqual(solution([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6);
});
test('원소가 하나면 그 값을 반환한다', () => {
assert.strictEqual(solution([1]), 1);
});
test('전체가 양수면 전체 합이 최대다', () => {
assert.strictEqual(solution([5, 4, -1, 7, 8]), 23);
});
test('전체가 음수면 가장 큰(절댓값이 작은) 음수를 반환한다', () => {
assert.strictEqual(solution([-3, -1, -4]), -1);
});node --test coding-test/13-dynamic-programming/02-max-subarray-sum/solution.test.js함정
- 배열 전체가 음수인 경우를 놓치고
best를 0으로 초기화하면 틀립니다. 반드시nums[0]으로 시작해야 “구간 길이 1 이상”이라는 조건을 지킵니다. current가 음수가 되어도 무조건 이어 붙이면 안 됩니다.Math.max(nums[i], current + nums[i])로 매번 “새로 시작할지” 비교해야 합니다.
문제 3. 무게 제한 안에서 최대 가치 담기
문제 설명
무게와 가치가 정해진 물건 여러 개와 배낭이 담을 수 있는 최대 무게(용량)가 주어집니다. 각 물건은 통째로 담거나 아예 담지 않아야 합니다(쪼갤 수 없음). 배낭 용량을 넘지 않으면서 담은 물건의 가치 합을 최대로 만드는 값을 구합니다.
| 제약 | 값 |
|---|---|
| 물건 개수 | 1 이상 100 이하 |
| 무게·가치·용량 | 각각 1 이상 1000 이하인 정수 |
입출력 예
| 입력 | 출력 | 설명 |
|---|---|---|
items = [{weight:2,value:3},{weight:3,value:4},{weight:4,value:5},{weight:5,value:6}], capacity=5 | 7 | 무게 2와 3짜리를 담아 가치 3+4=7 |
위와 같은 items, capacity=10 | 13 | 무게 3과 5, 또는 무게 2와 3과 4 조합으로 13 |
접근
dp[i][w]를 “물건 i개까지 고려했을 때 용량 w에서 담을 수 있는 최대 가치”로 정의합니다. i번째 물건의 무게가 w보다 크면 담을 수 없으므로 dp[i][w] = dp[i-1][w]입니다. 담을 수 있으면 “안 담았을 때”(dp[i-1][w])와 “담았을 때”(dp[i-1][w-weight] + value) 중 큰 값을 선택합니다. 물건 수를 n, 용량을 W라 하면 2차원 배열을 모두 채워야 하므로 시간·공간 복잡도 모두 O(n·W)입니다.
풀이
// coding-test/13-dynamic-programming/03-knapsack/solution.js
// 시간복잡도: O(n * W) — 물건 n개, 용량 W인 2차원 dp 테이블을 한 칸씩 채운다
// 공간복잡도: O(n * W) — dp 테이블 전체를 저장한다
export function solution(items, capacity) {
const itemCount = items.length;
const dp = Array.from({ length: itemCount + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= itemCount; i++) {
const { weight, value } = items[i - 1];
for (let w = 0; w <= capacity; w++) {
if (weight > w) {
dp[i][w] = dp[i - 1][w];
} else {
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight] + value);
}
}
}
return dp[itemCount][capacity];
}테스트
// coding-test/13-dynamic-programming/03-knapsack/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
const items = [
{ weight: 2, value: 3 },
{ weight: 3, value: 4 },
{ weight: 4, value: 5 },
{ weight: 5, value: 6 },
];
test('용량 5에서 최대 가치는 7', () => {
assert.strictEqual(solution(items, 5), 7);
});
test('용량 10에서 최대 가치는 13', () => {
assert.strictEqual(solution(items, 10), 13);
});
test('용량이 가장 가벼운 물건보다 작으면 0', () => {
assert.strictEqual(solution(items, 1), 0);
});node --test coding-test/13-dynamic-programming/03-knapsack/solution.test.js함정
- 배열을
Array(itemCount + 1).fill(new Array(capacity + 1).fill(0))처럼 만들면 모든 행이 같은 배열을 참조합니다. 반드시Array.from({ length }, () => ...)로 행마다 새 배열을 만듭니다. dp[i - 1][w - weight]에서w - weight가 음수가 되지 않는지(weight > w조건으로 먼저 걸러졌는지) 확인합니다.
문제 4. 가장 긴 증가하는 부분열의 길이
문제 설명
정수 배열이 주어질 때, 원래 순서를 유지하면서 원소를 골라 만든 부분열 중 값이 계속 증가하는 부분열(연속하지 않아도 됨)의 최대 길이를 구합니다.
| 제약 | 값 |
|---|---|
| 배열 길이 | 1 이상 2500 이하 |
입출력 예
| 입력 | 출력 | 설명 |
|---|---|---|
| [10, 9, 2, 5, 3, 7, 101, 18] | 4 | [2, 3, 7, 101] 또는 [2, 3, 7, 18] |
| [0, 1, 0, 3, 2, 3] | 4 | [0, 1, 2, 3] |
| [7, 7, 7, 7] | 1 | 모두 같은 값이면 길이 1(엄격히 증가해야 함) |
접근
dp[i]를 “i번째 원소로 끝나는 증가 부분열 중 가장 긴 길이”로 정의합니다. i보다 앞선 모든 j에 대해 nums[j] < nums[i]이면 dp[i]는 dp[j] + 1이 될 수 있으므로, 가능한 j 중 dp[j]가 가장 큰 값을 골라 dp[i] = max(dp[j]) + 1로 정합니다. 모든 i, j 쌍을 확인하므로 시간 복잡도는 O(n²), 공간 복잡도는 O(n)입니다. 정답은 dp 배열 전체의 최댓값입니다(가장 긴 부분열이 배열 끝에서 끝난다는 보장이 없기 때문입니다).
풀이
// coding-test/13-dynamic-programming/04-longest-increasing-subsequence/solution.js
// 시간복잡도: O(n^2) — 모든 i, j 쌍을 확인한다
// 공간복잡도: O(n) — dp 배열에 각 인덱스까지의 최장 길이를 저장한다
export function solution(nums) {
if (nums.length === 0) return 0;
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}테스트
// coding-test/13-dynamic-programming/04-longest-increasing-subsequence/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('일반적인 배열에서 길이 4를 찾는다', () => {
assert.strictEqual(solution([10, 9, 2, 5, 3, 7, 101, 18]), 4);
});
test('중간에 끝나는 부분열이 최댓값일 수 있다', () => {
assert.strictEqual(solution([0, 1, 0, 3, 2, 3]), 4);
});
test('모두 같은 값이면 길이 1이다', () => {
assert.strictEqual(solution([7, 7, 7, 7]), 1);
});
test('빈 배열이면 0을 반환한다', () => {
assert.strictEqual(solution([]), 0);
});node --test coding-test/13-dynamic-programming/04-longest-increasing-subsequence/solution.test.js함정
- “가장 긴 증가하는 부분열의 길이”를 배열의 마지막 원소를 기준으로만 찾으면 안 됩니다. 정답은
dp전체의 최댓값입니다. nums[j] < nums[i]를nums[j] <= nums[i]로 잘못 쓰면 같은 값도 증가로 인정해 버립니다. 문제가 “엄격히 증가”를 요구하는지 항상 확인합니다.
직접 해보기
- 문제 1의
solution(countWaysToClimb)을 배열 전체를 저장하지 않고 직전 두 값만 변수로 기억하도록 바꿔 공간 복잡도를 O(1)로 줄여봅니다. - 문제 3의
solution(maxKnapsackValue)이 실제로 어떤 물건을 담았는지도 함께 반환하도록,dp테이블을 거꾸로 추적하는 로직을 추가해봅니다.
정답 보기(1번)
// coding-test/13-dynamic-programming/01-climb-stairs/solution.js (공간 최적화 버전)
export function solution(n) {
if (n <= 1) return 1;
let previous = 1;
let current = 1;
for (let i = 2; i <= n; i++) {
const next = current + previous;
previous = current;
current = next;
}
return current;
}배열 대신 변수 두 개(previous, current)만 유지해 직전 값을 기억합니다. 결과는 같지만 공간 복잡도가 O(n)에서 O(1)로 줄어듭니다.
자주 하는 실수
| 증상 | 원인 | 고치는 법 |
|---|---|---|
DP 배열 인덱스에서 undefined + 숫자가 NaN이 됨 | 초기값(dp[0], dp[1] 등)을 빠뜨림 | 점화식을 세우기 전에 초기값부터 채운다 |
| 2차원 배열의 모든 행이 같은 값으로 바뀜 | fill(new Array(...))로 배열을 참조 공유시킴 | Array.from({ length }, () => new Array(...))로 행마다 새로 생성 |
정답을 dp 배열의 마지막 값으로만 찾아 틀림 | 최적 구간이 배열 끝에서 끝난다고 가정 | 문제 성격에 따라 dp 전체의 최댓값을 확인한다(문제 4) |
| 재귀로 짠 메모이제이션이 큰 입력에서 스택 오버플로 | 재귀 깊이가 입력 크기만큼 커짐 | 반복문 기반 타뷸레이션으로 바꾼다 |