커리큘럼/페이즈 4 · 심화 알고리즘
19주차

DP 입문 (1차원)

점화식을 세우는 절차를 손에 붙여요. 상태 → 전이 → 초기값 → 순서.

개념

DP는 어렵게 느껴지지만, 하는 일은 한 번 푼 문제의 답을 적어 두고 다시 안 푸는 것뿐이에요. 계단을 오르는데 '5번째 칸까지 오는 방법'이 궁금하면, '4번째까지 오는 방법'과 '3번째까지 오는 방법'을 더하면 돼요. 그 둘도 같은 방식으로 더 작은 답에서 나와요. 작은 답부터 표에 적어 두면, 큰 답은 표를 더하기만 하면 나와요.9주차에 그리디가 지는 걸 봤어요. 후회 없는 선택을 하려면 모든 경우를 따져야 하는데, 그냥 따지면 지수 시간이에요. 동적 계획법(DP)은 이미 계산한 하위 문제를 다시 계산하지 않음으로써 그것을 다항 시간으로 만들어요. 쓸 수 있는 조건은 13주차 재귀에서 이미 봤어요. 중복되는 하위 문제가 있고(피보나치), 하위 문제의 최적해로 전체 최적해를 만들 수 있으면 돼요.

점화식 세우는 4단계

DP가 어려운 이유는 아이디어가 매번 달라 보이기 때문인데, 절차는 항상 같아요. 이 순서대로 종이에 써요.
  1. 상태 정의 — dp[i]가 무엇인지 한 문장으로. 여기서 대부분 판가름 나요
  2. 전이 — dp[i]를 더 작은 dp로 어떻게 표현하나요
  3. 초기값 — 가장 작은 경우의 답을 직접 채워요
  4. 계산 순서 — dp[i]를 구할 때 필요한 값이 이미 채워져 있도록
1번을 대충 넘기면 나머지가 전부 꼬여요. 'dp[i]는 i번째까지 봤을 때의 최댓값'처럼 애매한 정의를 피하고, 'dp[i]는 i번째를 반드시 쓸 때의 최댓값'처럼 조건을 붙여 정확히 적어요.

탑다운과 바텀업

탑다운 (메모이제이션)바텀업 (타뷸레이션)
형태재귀 + 캐시반복문 + 배열
장점점화식을 그대로 옮기면 돼요스택 걱정 없고, 보통 더 빨라요
단점재귀 깊이 제한계산 순서를 직접 정해야 해요
언제상태가 듬성듬성할 때상태를 전부 채울 때
처음에는 탑다운으로 점화식을 확인하고, 통과하면 바텀업으로 바꿔 보는 연습을 권해요. 둘의 대응 관계가 보이기 시작하면 DP가 훨씬 쉬워져요.

대표 점화식

문제상태전이
계단 오르기dp[i] = i번째 칸에 도달하는 방법 수dp[i] = dp[i-1] + dp[i-2]
도둑질dp[i] = i번째 집까지의 최대 금액dp[i] = max(dp[i-1], dp[i-2] + a[i])
거스름돈dp[x] = x원을 만드는 최소 동전 수dp[x] = min(dp[x-c] + 1)
LISdp[i] = i를 마지막으로 쓰는 최장 길이dp[i] = max(dp[j] + 1), j < i이고 a[j] < a[i]

직접 채워 보기: 계단 오르기

한 번에 1칸이나 2칸을 오를 수 있을 때, 5번 칸에 오는 방법이 몇 가지인지 표를 채워 볼게요. dp[i]는 'i번 칸에 도달하는 방법 수'예요. i번 칸은 (i−1)번에서 한 칸, (i−2)번에서 두 칸 뛰어야만 닿으니까 dp[i] = dp[i-1] + dp[i-2]가 돼요. 가장 작은 두 칸만 손으로 채우면, 나머지는 앞의 두 칸을 더하기만 하면 나와요.
계단 5칸 — dp 표가 왼쪽부터 채워지는 과정
i      0   1   2   3   4   5
dp     1   1   .   .   .   .     ← 초기값만 채운 상태
​
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8
​
i      0   1   2   3   4   5
dp     1   1   2   3   5   8     → 답 dp[5] = 8
표를 왼쪽부터 채웠다는 게 계산 순서의 뜻이에요. dp[5]를 구할 때 dp[4]와 dp[3]이 이미 적혀 있어야 하니까요. 순서만 지키면 각 칸은 딱 한 번씩만 계산해요. 그래서 O(n)이에요.

패턴 코드

바텀업 기본형
javascript
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
  dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
최솟값 DP — 불가능한 값으로 초기화
javascript
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let x = 1; x <= amount; x++) {
  for (const c of coins) {
    if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
  }
}
return dp[amount] === Infinity ? -1 : dp[amount];
탑다운 (메모이제이션)점화식을 그대로 옮길 수 있어 처음 검증할 때 편해요.
javascript
const memo = new Map();
function solve(i) {
  if (i <= 1) return 1;
  if (memo.has(i)) return memo.get(i);
  const value = solve(i - 1) + solve(i - 2);
  memo.set(i, value);
  return value;
}

이번 주 문제

이번 주 진행0 / 4
주차 진행률
이번 주 주제로 골라둔 문제예요. 채점은 프로그래머스에서 하고, 풀고 나면 여기에 체크해 두세요. 난이도 순으로 보여줘요.
프로그래머스 진행률
  • 2 x n 타일링
    Lv. 2풀기
  • 땅따먹기
    Lv. 2풀기
  • 등굣길
    Lv. 3풀기
  • 정수 삼각형
    Lv. 3풀기

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.
  1. 지금 푼 문제에서 dp[i]가 무엇인지 한 문장으로 말할 수 있나요?
  2. 최솟값 DP에서 배열을 0으로 초기화하면 왜 틀리나요?
  3. 탑다운과 바텀업 중 어느 쪽을 언제 고르나요?
← 18주차 · 힙과 우선순위 큐20주차 · DP 심화 (2차원) →