🧠 Dynamic Programming(DP) 완전 정복
1. DP란?
DP(Dynamic Programming)은 복잡한 문제를 작은 문제로 나누고,
중복 계산을 피하기 위해 이전 계산 결과를 저장해서 푸는 알고리즘 기법입니다.
✔️ 핵심 아이디어:
- 한 번 푼 문제는 저장해두고
- 다시는 계산하지 않기
2. 언제 DP를 쓸까?
DP는 다음 두 조건을 만족해야 사용 가능합니다.
| 조건 | 설명 |
|---|---|
| ✅ Overlapping Subproblems | 같은 문제를 여러 번 푸는 구조 |
| ✅ Optimal Substructure | 큰 문제의 최적해가 작은 문제의 최적해로 구성됨 |
📌 예: 피보나치 수열, 격자 경로, 배낭 문제 등
3. 왜 써야 할까?
- 완전 탐색보다 효율적
- 중복 계산 제거 → 시간 복잡도 감소
- 많은 최적화/카운팅 문제 해결 가능
| 방식 | 시간 복잡도 |
|---|---|
| 완전탐색 | O(2^n) |
| DP 사용 | O(n) 또는 O(n^2) |
4. 구현 방식
🔁 Top-Down (재귀 + 메모이제이션)
dp = [-1] * 100
def fib(n):
if n <= 1:
return n
if dp[n] != -1:
return dp[n]
dp[n] = fib(n-1) + fib(n-2)
return dp[n]📈 Bottom-Up (반복문 + DP 테이블)
dp = [0] * 100
dp[1] = 1
for i in range(2, 100):
dp[i] = dp[i-1] + dp[i-2]DP 테이블이란?
부분 문제의 정답을 저장하는 배열 or 딕셔너리
📦 구조 예시
| 문제 | 테이블 예시 |
|---|---|
| 피보나치 | dp[i] |
| 격자 이동 | dp[i][j] |
| 상태 여러 개 | dp[i][j][k] |
❗ 문제에 따라 정답이 항상 dp[N][M]에 있는 게 아닐 수 있음.
→ 마지막 줄 전체에서 max(dp[i]) 등으로 구해야 하는 경우도 많음.
5. 실전 예제로 감 잡아보기
🪜 예제 1. 피보나치 수열 (기본 중 기본)
n번째 피보나치 수를 구해라
(단, f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2))
✅ Top-Down 방식
dp = [-1] * 100
def fib(n):
if n <= 1:
return n
if dp[n] != -1:
return dp[n]
dp[n] = fib(n-1) + fib(n-2)
return dp[n]✅ Bottom-Up 방식
dp = [0] * 100
dp[1] = 1
for i in range(2, 100):
dp[i] = dp[i-1] + dp[i-2]✔️ 핵심은 dp[n]에 이전 계산 결과 저장하는 구조
✔️ 반복되는 계산을 없애는 게 포인트
🧗 예제 2. 계단 오르기 (백준 2579)
한 번에 1칸 또는 2칸 오를 수 있을 때,
각 계단마다 점수가 있고, 연속 3칸은 못 오름
→ 얻을 수 있는 점수의 최댓값을 구해라
✅ 점화식 핵심
dp[i] = max(
dp[i-2] + score[i], # 한 칸 건너뛰고 오는 경우
dp[i-3] + score[i-1] + score[i] # 두 칸 건너오고 연속 두 칸 오르는 경우
)✅ Bottom-Up 예시
score = [0] + list(map(int, input().split()))
n = len(score) - 1
dp = [0] * (n + 1)
dp[1] = score[1]
if n >= 2:
dp[2] = score[1] + score[2]
for i in range(3, n + 1):
dp[i] = max(dp[i-2] + score[i], dp[i-3] + score[i-1] + score[i])✔️ 이 문제는 조건 처리가 중요함 → 연속 3칸 금지
✔️ 점화식이 문제의 조건을 정확히 반영하는 게 핵심
💸 예제 3. 동전 1 (백준 2293)
동전 종류가 여러 개 있을 때,
특정 금액을 만드는 경우의 수를 구해라 (순서 상관없이)
✅ 점화식 구조
dp[i] += dp[i - coin] # coin 하나 더 써서 i 만드는 경우 추가✅ Bottom-Up 예시
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [0] * (k + 1)
dp[0] = 1 # 0원을 만드는 경우의 수는 1
for coin in coins:
for i in range(coin, k + 1):
dp[i] += dp[i - coin]✔️ 이건 조합 문제 → 순서 상관 없음
✔️ coin 루프가 바깥에 있는 이유도 이 때문
🎒 예제 4. 0/1 배낭 문제 (Knapsack)
각 아이템은 무게와 가치가 있고, 배낭의 최대 용량은 W
일부 아이템만 골라서, 가치의 합이 최대가 되도록 선택하라
✅ 점화식 구조
dp[i][w] = max(
dp[i-1][w], # i번째 물건을 안 담음
dp[i-1][w - weight[i]] + value[i] # i번째 물건을 담음
)✅ Bottom-Up 예시
n, k = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = items[i - 1]
for j in range(k + 1):
if j < w:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)✔️ 2차원 DP 테이블
✔️ 물건을 하나씩 고려하며 담을지 말지 결정하는 구조
🔚 마무리 팁
- DP 문제는 상태 정의 + 점화식 이 두 가지가 전부임
- 처음엔 어려워도, 유형별 패턴이 눈에 익으면 진짜 할만해짐
- 실전에서는 Top-Down보단 Bottom-Up이 더 안정적임 (재귀 깊이 제한 X)
그리고 중요한 거 하나,
“이게 진짜 DP가 맞는가?” 싶으면
같은 계산 반복하고 있는지부터 의심해봐야 한다.
