동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제(subproblem)로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 피하는 최적화 기법이다. 메모이제이션(Memoization) 또는 상향식 접근법(Bottom-up)을 사용하여 연산 속도를 향상시킬 수 있다.
개요
동적 계획법은 다음 두 가지 속성을 가진 문제를 해결하는 데 적합하다.
- 최적 부분 구조(Optimal Substructure)
- 문제를 작은 하위 문제로 나누어 해결할 수 있으며, 부분 문제의 최적해를 결합하여 전체 문제의 최적해를 구할 수 있음.
- 중복 부분 문제(Overlapping Subproblems)
- 동일한 하위 문제가 여러 번 반복해서 등장하며, 이를 저장하여 재사용할 수 있음.
동적 계획법의 유형
동적 계획법은 메모이제이션(Top-Down)과 상향식 접근법(Bottom-Up) 두 가지 방식으로 구현할 수 있다.
메모이제이션(Top-Down)
- 재귀 호출을 이용하여 필요한 부분 문제만 계산.
- 중복 계산을 방지하기 위해 해시 테이블이나 배열을 사용하여 결과를 저장.
상향식 접근법(Bottom-Up)
- 작은 문제부터 해결하고, 그 결과를 이용해 더 큰 문제를 해결.
- 반복문을 사용하며, 테이블(Table)을 통해 값을 저장.
예제 문제
가장 대표적인 동적 계획법 문제 중 하나는 피보나치 수열(Fibonacci Sequence)이다.
재귀(Top-Down) 방식
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
print(fibonacci_memo(10)) # 출력: 55
반복(Bottom-Up) 방식
def fibonacci_tabulation(n):
if n <= 1:
return 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(fibonacci_tabulation(10)) # 출력: 55
동적 계획법이 적용되는 문제
동적 계획법은 다양한 최적화 문제에 사용된다.
- 배낭 문제(Knapsack Problem)
- 제한된 용량 내에서 최대 가치를 얻도록 아이템을 선택하는 문제.
- 최장 공통 부분 수열(LCS, Longest Common Subsequence)
- 두 개의 문자열에서 공통 부분 문자열의 최대 길이를 찾는 문제.
- 최소 편집 거리(Edit Distance)
- 문자열을 변환하는 최소 연산 횟수를 구하는 문제.
- 동전 교환 문제(Coin Change)
- 최소한의 동전 개수로 특정 금액을 만드는 문제.
- 여행하는 외판원 문제(TSP, Traveling Salesman Problem)
- 모든 도시를 한 번씩 방문하는 최소 비용의 경로를 찾는 문제.
시간 복잡도
동적 계획법을 사용하면 여러 문제를 효율적으로 해결할 수 있다.
- 피보나치 수열
- 일반 재귀: O(2ⁿ)
- 동적 계획법: O(n)
- 배낭 문제
- 일반적인 완전 탐색: O(2ⁿ)
- 동적 계획법: O(nW) (W는 배낭 용량)
- LCS
- 완전 탐색: O(2ⁿ)
- 동적 계획법: O(nm) (n과 m은 두 문자열 길이)
응용
동적 계획법은 다양한 분야에서 활용된다.
- 데이터 압축
- 문자열 비교 및 패턴 매칭.
- 네트워크 최적화
- 최적 경로 탐색 및 패킷 전송 최적화.
- 게임 인공지능
- 최적의 움직임을 찾는 알고리즘.
같이 보기
참고 문헌
- Bellman, Richard. "Dynamic Programming." Princeton University Press, 1957.
- Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.