Note
동적 프로그래밍을 통해 중복 계산을 제거하고 효율적으로 문제를 해결하는 기법에 대해 알아봅니다.
문제 상황
재귀 함수를 사용하여 문제를 해결할 때, 같은 계산을 여러 번 반복하는 경우가 있습니다.
예를 들어 피보나치 수열을 재귀적으로 계산하면:
fib(5)를 계산하기 위해fib(4)와fib(3)을 호출fib(4)를 계산하기 위해fib(3)과fib(2)를 호출fib(3)이 여러 번 중복 계산됨!
이런 중복 계산은 시간 복잡도를 지수적으로 증가시킵니다.
동적 프로그래밍이란?
**동적 프로그래밍(Dynamic Programming, DP)**은 큰 문제를 작은 하위 문제로 나누어 해결하되, 한 번 계산한 결과를 저장해 재사용하는 기법입니다.
핵심 아이디어
- 하위 문제의 중복: 같은 하위 문제가 여러 번 나타남
- 결과 저장: 계산한 결과를 배열이나 딕셔너리에 저장
- 재사용: 같은 문제를 다시 계산하지 않고 저장된 값을 사용
피보나치 수열 예시
재귀 호출 방식 (비효율적)
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n - 1) + fib(n - 2)시간 복잡도: O(2^n) - 지수 시간
fib(5)를 계산하기 위해fib(3)이 2번,fib(2)가 3번 호출됨- n이 커질수록 중복 계산이 기하급수적으로 증가
동적 프로그래밍 방식 (효율적)
def fibonacci(n):
d = [0] * (n + 1)
d[1] = 1
d[2] = 1
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
return d[n]시간 복잡도: O(n) - 선형 시간
- 각 값을 한 번만 계산하고 저장
- 이후에는 저장된 값을 재사용
동적 프로그래밍의 두 가지 접근법
1. Bottom-Up (상향식)
작은 문제부터 차례대로 해결하여 큰 문제를 해결합니다.
# 피보나치 수열 예시
d = [0] * (n + 1)
d[1] = 1
d[2] = 1
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]장점:
- 반복문 사용으로 스택 오버플로우 위험이 없음
- 일반적으로 더 빠름
2. Top-Down (하향식, 메모이제이션)
재귀 호출을 사용하되, 계산한 결과를 저장해 재사용합니다.
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n == 1 or n == 2:
return 1
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]장점:
- 필요하지 않은 하위 문제는 계산하지 않음
- 재귀적 사고가 자연스러움
동적 프로그래밍 적용 조건
동적 프로그래밍을 적용할 수 있는 문제는 다음 조건을 만족해야 합니다:
- 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해로 구성됨
- 중복되는 하위 문제 (Overlapping Subproblems): 같은 하위 문제가 여러 번 나타남
시간 복잡도 비교
피보나치 수열 계산 시:
| 방법 | 시간 복잡도 | n=30일 때 실행 횟수 |
|---|---|---|
| 재귀 호출 | O(2^n) | 약 832,040번 |
| 동적 프로그래밍 | O(n) | 28번 |
동적 프로그래밍이 훨씬 효율적입니다!
활용 예시
동적 프로그래밍은 다음과 같은 문제에서 유용합니다:
- 피보나치 수열 계산
- 최장 공통 부분 수열 (LCS)
- 배낭 문제 (Knapsack Problem)
- 최단 경로 문제
- 동전 교환 문제
관련 문제
- BOJ 24416: 알고리즘 수업 - 피보나치 수 1 - 재귀 호출 vs 동적 프로그래밍 비교