동적 계획법 (Dynamic Programming, DP)

큰 문제를 작은 문제로 나누어 풀고, 중복 계산을 줄여 효율적으로 해결하는 알고리즘 기법

---

🚀 동적 계획법(DP)이란?

✅ 큰 문제를 작은 하위 문제로 나누어 푸는 방식
✅ 이전에 계산한 결과를 저장하여 중복 계산을 줄임 → 메모이제이션(Memoization) 사용 /  메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가
✅ "최적 부분 구조(Optimal Substructure)"와 "중복되는 부분 문제(Overlapping Subproblems)"가 존재할 때 사용 가능

 

🚀 DP의 두 가지 접근 방법

1️⃣ Top-Down (재귀 + 메모이제이션)

• 큰 문제를 작은 문제로 나누어 푸는 방식
• 재귀 + 딕셔너리(memo) 또는 리스트(dp[])를 사용하여 중복 계산을 줄임

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]

n = 10
dp = [-1] * (n + 1)  # 메모이제이션 배열 초기화
print(fib(n))  # 55

✅ 재귀적으로 값을 저장하면서 계산하는 방식

---

2️⃣ Bottom-Up (반복문 + DP 테이블)

• 작은 문제부터 차근차근 계산하여 큰 문제를 해결하는 방식
• 배열을 만들어 이전 값을 저장하며 반복문으로 해결

n = 10
dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n])  # 55

✅ 반복문을 사용하여 효율적으로 계산 (O(N))
✅ 스택 오버플로우 문제 없음 (재귀 없이 반복문 사용)

 

🎯 DP 문제를 푸는 방법 (패턴)

1️⃣ "최적 부분 구조"와 "중복되는 부분 문제"가 있는지 확인
2️⃣ Bottom-Up (반복문) 또는 Top-Down (재귀+메모이제이션) 방식 선택
3️⃣ DP 테이블(dp[] 리스트) 생성하여 값을 저장
4️⃣ 점화식(Recurrence Relation) 도출하여 dp[i]를 채움
5️⃣ 최종적으로 dp[n]을 반환하여 문제 해결

 

 

✅ DP vs Greedy vs 완전 탐색 비교

알고리즘	특징	문제 유형
완전 탐색 (Brute Force)	모든 경우의 수를 계산 (비효율적)	작은 데이터 크기, 모든 경우를 탐색해야 할 때
그리디 (Greedy)	현재 최적 선택이 미래에도 최적이어야 함	동전 거스름돈, 최단 경로
DP (Dynamic Programming)	중복 계산을 피하며 최적해를 구함	피보나치 수열, 최소 비용 문제, 경로 찾기

 

🚀 결론

✅ 동적 계획법(DP)은 "이전 값을 저장하여 중복 계산을 줄이는 방식"
✅ "최적 부분 구조"와 "중복되는 부분 문제"가 있을 때 적용 가능
✅ Top-Down(재귀 + 메모이제이션) / Bottom-Up(반복문 + DP 테이블) 방식 사용 가능
✅ 완전 탐색이나 그리디로 해결할 수 없는 문제에서 DP를 고려해야 함 🚀