동적 프로그래밍에는 두 가지 접근 방법이 있습니다.
두 접근 방법의 공통점은 다음과 같습니다.
반복되는 계산을 줄이고, 하위 문제들을 위한 해결 방안을 메모리에 저장
- 하위 문제에 대해 이미 해결되었는지를 확인한다.
2.1 이미 해결되었다면, 해당 값을 리턴하여 상위 문제를 연산한다.
2.2 만일 해결되지 않았다면 일반적인 방법으로 하위 문제를 해결한다.
가장 하위 문제를 찾아 해당 값을 찾아 넣어주는 방법이 되겠네요
일반적으로 재귀 호출을 통한 memorize 라고 합니다.
Top-down은 하위 문제를 재귀를 이용해 한번만 더 작은 하위 문제(이전 하위 문제)를 통해 해결된다고 가정하고 코드를 구성합니다.
구현 난이도는 Top-down이 일반적으로는 쉽다고 합니다.
Top-down은 재귀함수이기 때문에 Bottom-up보다 느립니다.
충분히 큰 모든 N 에 대하여 두 접근방식은 일반적으로 동일한 시간 복잡도를 가집니다.
Bottom-up 을 사용하면 시간 및 공간 복잡성을 더욱 최적화 할 수 있습니다. ( 반복문 내의 가지치기 )
앞서 말씀드린 Combination에 대해 두 가지 접근 방식에 따라 DP로 구현해 보겠습니다.
# Top-down
import sys, time
start = time.time()
sys.setrecursionlimit(10000)
DP = [[0] * 1001 for i in range(1001)]
def combination(n, r):
if r == 0 or r == n:
DP[n][r] = 1
if not DP[n][r]:
DP[n][r] = combination(n - 1, r - 1) + combination(n - 1, r)
return DP[n][r]
print(combination(1000, 35))
end = time.time()
print(end - start)
# 결과 값 : 53007599712421378893801108296363791932591235151324218238066214600
# 시간 : 0.11594009399414062
import time
start = time.time()
DP = [[0] * 1001 for i in range(1001)]
for n in range(0, 1001):
for r in range(0, n + 1):
if r == 0 or n == r: DP[n][r] = 1
else:
DP[n][r] = DP[n - 1][r - 1] + DP[n-1][r]
print(DP[1000][35])
end = time.time()
print(end - start)
# 결과 값 : 53007599712421378893801108296363791932591235151324218238066214600
# 시간 : 0.655327320098877
출처 : https://www.enjoyalgorithms.com/blog/top-down-memoization-vs-bottom-up-tabulation
ㅇwㅇ