PostsSeriesLabsAlgo

DP

1차원 DP

계단을 오르는 경우의 수

시작 자리(0번)에서 한 번에 1칸 또는 2칸씩 올라 6번째 계단까지 갑니다. 아래 표에는 계단마다 올라가는 방법이 몇 가지인지 적습니다. 0번 계단까지는 1가지, 1번 계단까지도 1가지(한 칸 오르기뿐)라고 적혀 있습니다.

먼저 맞혀 보세요. 4번째 계단까지는 몇 가지일까요?

계단까지 올라가는 방법의 수 (작은 숫자가 계단 번호)

채운 칸 0/5

내 예상 0가지 · 실제 0가지 → 달랐어요

1 → 1 → 2 → 3 → 5 → 8 → 13표를 채운 순서입니다. 2번 칸부터는 앞 두 칸을 더한 값입니다.

계단 50칸 · 길을 하나씩 세기20,365,011,074번
계단 50칸 · 표 채우기49칸
오르는 방법이 20,365,011,074가지라 하나씩 세면 컴퓨터로 34분입니다. 표는 1초 안에 끝납니다.

작은 문제의 답을 표에 채우며 큰 문제의 답까지 올라가는 방법 = 1차원 DP (동적 계획법, dynamic programming)

  • 칸의 값 — 앞 두 칸의 합. 이 관계를 점화식(recurrence)이라고 부른다
  • 1 1 2 3 5 8 13 — 앞 장 메모이제이션의 피보나치 수열과 같은 수열이다

앞 칸의 답이 있으면 지금 칸이 정해진다

  • 지금 칸의 답 — 마지막 걸음이 한 칸이면 한 칸 아래, 두 칸이면 두 칸 아래에서 온다. 그 두 칸의 답을 더하면 된다
  • 앞에서부터 채우면 — 필요한 값이 늘 준비돼 있다. ①에서 앞 칸부터만 눌렸던 이유다
  • 한 번 구한 칸은 — 표에 적어 두고 다시 계산하지 않는다. 앞 장의 수첩을 위가 아니라 아래부터 채운 것이다

코드는 표를 앞에서부터 채우는 반복문이다

계단은 ①과 같은 6칸입니다. 다음을 눌러 한 줄씩 넘기며 칸이 하나씩 채워지는 걸 보세요.

다음을 눌러 한 줄씩 넘겨 보세요

n = 6

climb.py
  1. 1def climb(n):
  2. 2 dp = [0] * (n + 1)
  3. 3 dp[0] = dp[1] = 1
  4. 4 for i in range(2, n + 1):
  5. 5 dp[i] = dp[i - 1] + dp[i - 2]
  6. 6 return dp[n]
0 / 14
  • dp = [0] * (n + 1) — 0번부터 n번까지 n + 1칸. 아직 안 채운 칸은 0 이다
  • dp[0] = dp[1] = 1 — 시작 자리와 1번 계단은 1가지씩이다
  • dp[i - 1] + dp[i - 2] — 한 칸 아래와 두 칸 아래의 합이 i번 칸이다

한 번에 1칸, 2칸, 3칸을 오를 수 있다면 3번째 계단까지는 몇 가지일까요? 0번과 1번 칸은 그대로 1가지씩입니다.

초깃값과 0칸에서 틀린다

  • 초깃값을 0 으로 두면 — 둘 다 0 이면 표가 전부 0 이다. dp[0] 만 0 이면 6번 계단이 13가지가 아니라 8가지로 나온다. 오류도 안 난다
  • n = 0 이면 — dp[1] = 1 줄에서 IndexError: list assignment index out of range. n = 1 은 괜찮고 1 이 나온다
  • 재귀에 메모만 붙이면 — functools.lru_cache 로도 n = 5000 에서 RecursionError 가 난다. 기본 한도가 1000 이다. 앞에서부터 채우는 표는 5000 칸도 괜찮다
  • 답이 아주 커지면 — n = 1000 이면 209자리다. 문제는 보통 % 1_000_000_007 로 나눈 나머지를 묻는다. 칸마다 dp[i] = (dp[i - 1] + dp[i - 2]) % 1_000_000_007 로 적는다. 직접 재 보니 백만 칸을 0.05초에 채웠다(Python 3.14, 컴퓨터마다 다르다)

문제에서 이 말이 보이면

경우의 수를 센다앞 결과로 지금을 구한다n 이 크다 (1000 이상)

다음 장에서는 가방에 무엇을 담을지 고르는 0/1 배낭을 봅니다.