안녕하세요! 김코딩입니다
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누고, 한 번 해결한 문제의 결과를 저장하여 중복 계산을 피하는 알고리즘 기법입니다.
1. 동적 계획법이란?
DP는 **분할 정복(Divide and Conquer)과 메모이제이션(Memoization)**을 활용하여 문제를 효율적으로 해결하는 기법입니다.
🔹 분할 정복: 문제를 작은 하위 문제로 나누어 해결
🔹 메모이제이션: 한 번 계산한 값을 저장하여 중복 연산 방지
💡 적용 가능한 문제 특징:
✅ 최적 부분 구조 (Optimal Substructure): 문제를 작은 문제로 나눌 수 있어야 함
✅ 중복되는 부분 문제 (Overlapping Subproblems): 동일한 부분 문제가 반복되어 등장
2. 피보나치 수열을 활용한 DP 개념 이해
❌ 비효율적인 재귀(단순 분할 정복)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10)) # 결과: 55
🚨 위 코드의 문제점: 같은 값을 여러 번 계산하여 **시간 복잡도가 O(2ⁿ)**으로 증가
3. 동적 계획법 적용 (메모이제이션 사용)
방법 1: Top-Down 방식 (재귀 + 메모이제이션)
dp = {}
def fib_memo(n):
if n <= 1:
return n
if n not in dp:
dp[n] = fib_memo(n - 1) + fib_memo(n - 2) # 저장하여 중복 연산 방지
return dp[n]
print(fib_memo(10)) # 결과: 55
✅ 장점: 불필요한 연산을 제거하여 성능 향상 (시간 복잡도 O(N))
방법 2: Bottom-Up 방식 (반복문 + DP 테이블)
def fib_tabulation(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # 이전 값들을 이용하여 계산
return dp[n]
print(fib_tabulation(10)) # 결과: 55
✅ 장점: 메모이제이션보다 더 효율적인 O(N) 시간 복잡도
✅ 단점: O(N) 크기의 추가 메모리 필요
4. 동적 계획법 문제 예제: 최소 동전 개수 문제
💡 문제: N원을 만들기 위한 최소 동전 개수 구하기
- 사용할 수 있는 동전:
{1, 3, 4}
🔹 예제 입력: N = 6
🔹 예제 출력: 2 (4원 + 2원)
DP를 활용한 풀이 (Bottom-Up)
def min_coins(n, coins):
dp = [float('inf')] * (n + 1)
dp[0] = 0 # 0원을 만드는 데 필요한 동전 개수는 0
for i in range(1, n + 1):
for coin in coins:
if i >= coin:
dp[i] = min(dp[i], dp[i - coin] + 1) # 최소 개수 갱신
return dp[n] if dp[n] != float('inf') else -1
print(min_coins(6, [1, 3, 4])) # 결과: 2
✅ 시간 복잡도: O(N * len(coins))
✅ 공간 복잡도: O(N)
5. 동적 계획법 활용 분야
✔ 피보나치 수열
✔ 최소 비용 경로 문제 (Dijkstra 알고리즘)
✔ 배낭 문제 (Knapsack Problem)
✔ 최장 공통 부분 수열 (LCS, Longest Common Subsequence)
✔ 행렬 곱셈 순서 최적화 (Matrix Chain Multiplication)
6. 결론
✅ DP는 중복 계산을 줄여 알고리즘을 최적화하는 강력한 기법
✅ Top-Down (재귀 + 메모이제이션) vs Bottom-Up (반복문 + DP 테이블) 선택 가능
✅ 실전 문제 풀이에서 최적 부분 구조와 중복되는 부분 문제를 확인하는 것이 핵심
🎯 연습 추천 문제:
- 백준 1003번: 피보나치 함수
- 백준 1463번: 1로 만들기
- 백준 2579번: 계단 오르기
- 프로그래머스: 등굣길
🔥 다양한 DP 문제를 연습하며 실력을 키워보세요!