✅ 다이내믹 프로그래밍이란?
복잡한 문제를 더 작은 문제로 나눠서 풀고,
그 결과를 저장해두어 같은 계산을 반복하지 않는 방법이에요.
📦 핵심 개념 2가지
- 중복되는 하위 문제 (Overlapping Subproblems)
👉 같은 계산을 여러 번 반복하는 문제 - 최적 부분 구조 (Optimal Substructure)
👉 큰 문제의 최적해가 작은 문제들의 최적해로 구성되는 경우
이 두 가지가 있을 때 다이내믹 프로그래밍이 쓸 수 있어요.
🎯 예시로 쉽게 이해해보자 (피보나치 수열)
피보나치 수열은 다음과 같이 정의돼요:
f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2)❌ 나쁜 방법: 재귀만 쓰기 (중복 계산 많음)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)- fib(5)를 계산하려면 fib(4)와 fib(3) 필요하고,
- fib(4)를 계산하려면 다시 fib(3)과 fib(2) 필요하고…
👉 fib(3)을 여러 번 계산하게 돼요.
✅ 좋은 방법: 다이내믹 프로그래밍 사용
방법 1: 메모이제이션 (위에서 아래로)
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n <= 1:
memo[n] = n
else:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]방법 2: 탑다운 대신 바텀업 (아래에서 위로)
def fib(n):
dp = [0, 1] + [0]*(n-1)
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]👉 중복 계산 없이, 빠르게 결과를 구할 수 있어요.
🧩 DP로 풀 수 있는 대표 문제들
- 피보나치 수
- 계단 오르기
- 동전 교환
- 배낭 문제 (Knapsack)
- 최장 공통 부분 수열 (LCS)
- 문자열 편집 거리 (Edit Distance)
💡 기억하면 좋은 팁
- "큰 문제를 작은 문제로 나눌 수 있을까?"
- "작은 문제들의 결과를 저장해두고 재사용할 수 있을까?"
- "같은 계산을 여러 번 하지 않는 방법이 있을까?"
이 질문들이 들리면, DP를 생각하세요!
🔍 "작은 문제로 나눈다"는 건 어떤 뜻일까?
복잡한 문제를 조금 더 단순한 비슷한 문제들로 쪼개는 것이에요.
그리고 그 작은 문제들의 답을 이용해서 큰 문제의 답을 만들어내는 방식이죠.
🎯 예시 1: 계단 오르기 문제
🧗 한 번에 1칸 또는 2칸을 올라갈 수 있을 때,
N개의 계단을 오르는 방법의 수는 몇 가지일까?
예를 들어 n = 4일 때:
- 한 번에 1칸씩 4번 → 1+1+1+1
- 2칸 한 번 + 나머지는 1칸씩
- 2칸 두 번
(총 5가지)
이 문제를 작은 문제로 나눠볼 수 있어요:
- 계단 4칸을 오르는 방법 수는
👉 계단 3칸을 오르는 방법 수 + 계단 2칸을 오르는 방법 수
왜?
마지막에 한 칸 올라오려면 → 이전에 3칸까지 올라가 있었어야 하고
마지막에 두 칸 올라오려면 → 2칸까지 올라가 있었어야 하니까요.
f(n) = f(n-1) + f(n-2)즉, 큰 문제 f(4)를 f(3)과 f(2)라는 작은 문제로 나눈 것이에요.
🧗 문제 설명
계단이 총 n칸 있어요. 한 번에 1칸 또는 2칸씩만 오를 수 있어요.
이 계단을 꼭대기까지 올라가는 방법의 수는 총 몇 가지일까요?
예를 들어:
- n = 1 ➡️ 방법: 1 (1)
- n = 2 ➡️ 방법: 2 (1+1, 2)
- n = 3 ➡️ 방법: 3 (1+1+1, 1+2, 2+1)
🔍 작은 문제로 나누기
계단 n칸을 오르는 방법 수 f(n)은 다음과 같이 생각할 수 있어요:
f(n) = f(n-1) + f(n-2)
왜냐하면:
- 마지막에 1칸 올라왔다면 → f(n-1)까지 올라가 있었어야 함
- 마지막에 2칸 올라왔다면 → f(n-2)까지 올라가 있었어야 함
🧠 점화식 정리
f(0) = 1 (아무것도 안 올라가도 1가지 방법)
f(1) = 1 (1칸 오르기)
f(2) = 2 (1+1, 2)
f(n) = f(n-1) + f(n-2)✅ 파이썬 코드로 풀어보기 (Bottom-Up 방식)
def climb_stairs(n):
if n == 0 or n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]예시 실행:
print(climb_stairs(3)) # 출력: 3
print(climb_stairs(5)) # 출력: 8💡 추가 설명
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
피보나치 수열과 거의 같죠?
📌 연습 문제
이제 아래 문제도 도전해볼 수 있어요:
한 번에 1칸, 2칸, 또는 3칸씩 오를 수 있다면?
👉 점화식은 어떻게 바뀔까요?
✅ 문제 정리
한 번에 1칸, 2칸, 또는 3칸을 오를 수 있을 때
n칸 계단을 오르는 방법의 수를 구하는 문제
🧠 점화식
f(n) = f(n-1) + f(n-2) + f(n-3)이때, n이 음수가 되면 그건 의미 없는 경우이기 때문에
f(n) = 0 (음수인 경우)로 처리해주는 게 맞아요.
또한, 기본값(초기값)도 잘 설정해야 해요:
🔹 기본값
| 0 | 1 (아무것도 안 오르는 한 가지 방법) |
| 1 | 1 (1) |
| 2 | 2 (1+1, 2) |
✅ 파이썬 코드
def climb_stairs(n):
if n < 0:
return 0
if n == 0:
return 1 # 0칸은 1가지 방법 (아무것도 안함)
dp = [0] * (n + 1)
dp[0] = 1 # 기저 사례
if n >= 1:
dp[1] = 1
if n >= 2:
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
return dp[n]🔍 예시 실행
print(climb_stairs(3)) # 출력: 4 (1+1+1, 1+2, 2+1, 3)
print(climb_stairs(4)) # 출력: 7
🎓 정리
- f(n) = f(n-1) + f(n-2) + f(n-3)
- f(n < 0) = 0
- 기저 조건: f(0) = 1
이처럼 음수 입력은 0으로 간주하는 건 다이내믹 프로그래밍에서 자주 쓰는 테크닉이에요.
이제는 재귀 + 메모이제이션 방식으로 같은 계단 문제를 풀어볼 차례예요.
앞서 배운 점화식과 조건을 그대로 적용하되, 중복 계산을 피하기 위해 결과를 저장해두는 것이 핵심입니다.
🔁 재귀 + 메모이제이션 코드
def climb_stairs(n, memo={}):
if n < 0:
return 0
if n == 0:
return 1
if n in memo:
return memo[n]
memo[n] = (
climb_stairs(n - 1, memo) +
climb_stairs(n - 2, memo) +
climb_stairs(n - 3, memo)
)
return memo[n]
🔍 설명
- memo는 계산 결과를 저장해두는 딕셔너리입니다.
- n이 0이면 한 가지 방법 (아무것도 안 하기)
- n이 음수면 불가능한 경우이므로 0 반환
- 이미 계산한 n이 있다면 memo[n]에서 결과를 꺼내와서 중복 계산 방지
✅ 실행 예시
print(climb_stairs(3)) # 출력: 4
print(climb_stairs(5)) # 출력: 13
print(climb_stairs(10)) # 출력: 274📦 메모이제이션 없이 재귀로 풀었을 때 문제점
def bad_climb(n):
if n < 0:
return 0
if n == 0:
return 1
return bad_climb(n-1) + bad_climb(n-2) + bad_climb(n-3)이 방식은 n이 커지면 똑같은 값을 너무 많이 반복 계산하기 때문에
시간 복잡도가 급격히 증가해 느려지고 비효율적이에요.
🧠 한 줄 요약
재귀 + 메모이제이션은 "필요한 것만 계산하고, 한 번 계산한 건 저장해서 재활용한다"는 다이내믹 프로그래밍의 전형적인 형태예요.
🎯 예시 2: 최소 동전 개수 문제
💰 목표 금액을 만들기 위해 최소한의 동전을 사용하는 문제
예: 동전 종류가 [1, 3, 4]일 때 6원을 최소 몇 개로 만들 수 있을까?
💰 문제 설명: 최소 동전 개수 문제
동전 종류가 주어졌을 때, 목표 금액 amount를 만들기 위한 최소 동전 개수를 구하세요.
동전은 무한히 사용할 수 있어요.
만들 수 없다면 -1을 반환하세요.
📌 예시
coins = [1, 3, 4]
amount = 6- 가능한 조합:
- 1+1+1+1+1+1 (6개)
- 3+3 (2개)
- 4+1+1 (3개)
👉 최소 동전 수는 2개 (3+3)
🧠 점화식 아이디어
f(n) = 금액 n을 만들기 위한 최소 동전 개수
f(n) = min(f(n - coin) + 1) for coin in coins- +1은 현재 사용한 coin 하나
- n - coin은 남은 금액에 대한 최소 동전 수
✅ 재귀 + 메모이제이션 방식 (Top-down)
def coin_change(coins, amount, memo=None):
if memo is None:
memo = {}
if amount in memo:
return memo[amount]
if amount < 0:
return float('inf') # 만들 수 없는 경우
if amount == 0:
return 0 # 0원을 만들기 위한 동전 수는 0
min_count = float('inf')
for coin in coins:
res = coin_change(coins, amount - coin, memo)
if res != float('inf'):
min_count = min(min_count, res + 1)
memo[amount] = min_count
return min_count🧪 실행 예시
coins = [1, 3, 4]
amount = 6
result = coin_change(coins, amount)
print(result if result != float('inf') else -1)
# 출력: 2🔍 핵심 포인트 요약
- 목표 금액에서 각 동전을 하나씩 빼면서 작은 문제로 나아간다
- 메모이제이션을 사용해서 같은 금액에 대한 중복 계산을 막는다
- 금액이 0이면 0 리턴, 음수면 불가능한 경우로 inf 리턴
- 모든 경우 중에서 가장 적은 동전 수를 선택
이번엔 🎯 동전 문제의 바텀업 방식 (Bottom-up DP) 으로 풀어보겠습니다.
이 방식은 작은 문제부터 차례차례 답을 채워나가는 방식입니다.
🧠 점화식 정리
dp[x] = min(dp[x - coin] + 1) for coin in coins- dp[x]는 금액 x를 만들기 위한 최소 동전 수
- dp[0] = 0 (0원을 만들기 위한 동전 수는 0개)
✅ 바텀업 코드
def coin_change(coins, amount):
# amount + 1은 불가능한 큰 값으로 초기화 (무한대 역할)
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 0원을 만들기 위한 동전 수는 0
for x in range(1, amount + 1):
for coin in coins:
if x - coin >= 0:
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1🔍 실행 예시
coins = [1, 3, 4]
amount = 6
print(coin_change(coins, amount)) # 출력: 2📊 동작 흐름 예시 (dp[0]부터 dp[6]까지 계산)
| 0 | - | 0 |
| 1 | 1 | 1 |
| 2 | 1+1 | 2 |
| 3 | 3 / 1+1+1 | 1 |
| 4 | 4 / 1+3 / 1+1+1+1 | 1 |
| 5 | 1+4 / 2+3 / 1+1+3 | 2 |
| 6 | 3+3 / 4+1+1 / 1+1+1+3 | 2 |
📌 바텀업 방식 장점
- 모든 경우를 한 번만 계산하므로 속도 빠름
- 재귀 호출 스택 사용 안 하므로 메모리 안정적
- 실전 코딩 테스트에서 많이 쓰이는 방식!
'알고리즘 문제' 카테고리의 다른 글
| 💡 가장 빠르게 팰린드롬을 찾는 알고리즘, Manacher’s Algorithm (7) | 2025.07.10 |
|---|---|
| 다이내믹 프로그래밍(Dynamic Programming) 문제로 이해하기 (2) | 2025.07.09 |