다이나믹 프로그래밍(동적계획법)이란?
문제를 작은 하위 문제로 나누고, 그 결과를 저장해가며 전체 문제를 해결하는 최적화 기법
( 최적화 기법 = 하나의 알고리즘이 아니라, 여러 풀이과정에 사용될 수 있는 하나의 해결 기법)핵심 아이디어(DP 조건)
•
최적 부분 구조(Optimal Substructure) : 큰 문제의 최적해가 작은 문제의 최적해로 구성됨
•
중복되는 부분 문제(Overlapping Subproblems) : 동일한 하위 문제가 여러 번 반복
분할 정복과의 차이는?
동적 계획법(DP) | 분할 정복 | |
부분 문제 중복 | | |
하위 문제 저장 | (메모이제이션) | |
예시 | 피보나치, LIS | 병합정렬, 퀵정렬 |
분할정복처럼 문제를 서브 문제로 나누고 이를 해결해나가는 과정을 거칩니다. 다만 분할정복과의 차이점은, 다이나믹 프로그래밍의 경우 서브 문제가 겹치는 경우가 있는 반면 분할정복은 서브 문제가 겹치지 않고 독립적이라는 점입니다.
구현 방식
먼저 그냥 재귀함수로만 구현한다면 어떨까요?
N = int(input().strip())
def fibo(n):
if n <= 1:
return n
return fibo(n-1) + fibo(n-2)
Python
복사
이 풀이법은 올바른 답을 내놓긴 하지만 시간 초과가 발생합니다. 메모이제이션을 하지 않았기 때문인데요, 메모이제이션은 한 번 만든 답은 저장해뒀다가 또 사용한다로 생각해주시면 좋을 듯 합니다.
피보나치 수 문제는, 분할 정복과 유사하게 느껴집니다(주요 로직은 동일하다고도 말할 수 있겠습니다). 그러나 함수들의 인자값들을 보면, 분명 다른 지점에서 발생한 서브 문제이지만, 동일한 값을 뱉어내야하는 서브 문제입니다. 어차피 동일한 값을 리턴하는 거라면, 저장해뒀다가 재사용하는 게 훨씬 좋겠죠?
Top - Down(Memoization)
이 방식은 재귀함수를 사용해 큰 문제를 작은 문제로 바꿔나가며 해결합니다. 탑다운 방식이 해결하기가 좀 더 쉽지만, 재귀함수를 사용하기에 느리고 메모리 소모가 크다는 단점이 있습니다.
바로 위에서 재귀함수로만 구현했던 로직에서 좀 더 나아가보겠습니다. 어떻게 하면 저장했다가 재사용할 수 있을까요?
N = int(input().strip())
dp = [0] * (N + 1) # 0인덱스 ~ N인덱스 : 인덱스에 해당하는 인자값에 대한 결과를 값으로 저장
def fibo(n):
# 종료 조건
if n <= 1:
return n
# 메모이제이션 : 저장된 값이 있으면 즉시 반환
if dp[n] != 0:
return dp[n]
# 저장된 값이 없으면 새로운 값으로 갱신
dp[n] = fibo(n-1) + fibo(n-2)
return dp[n]
Python
복사
Bottom - Up(Tabluation)
이 방식은 반복문을 사용해 작은 문제들을 모아 큰 문제를 해결합니다. 바텀업 방식이 빠르기는 하지만 문제를 해결하는 점화식을 찾아내기는 상대적으로 어렵습니다.
탑다운 방식으로 구현했던 로직을 이번에는 바텀업 방식으로 변경해보겠습니다 :
n = int(input().strip())
def fibo(n):
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Python
복사
팁
•
점화식을 찾아내 수식으로 표현해내는 것이 매우 x 999 중요합니다. 점화식을 표현하지 못하면 DP 문제는 해결이 안됩니다.
•
DP는 알고리즘이 아니다보니, 여러 문제의 해결 방법 중 하나로 사용되는 기법입니다. 그러니 DP만을 사용하는 문제는 쉬운 문제에만 있고 난이도가 올라가면 최적화 용도로 DP가 껴있는 경우가 많습니다
참고 자료
