DP(Dynamic Programming)는 이전에 계산한 값을 저장해 놓고 재활용하여 중복 계산을 줄이는 알고리즘 기법입니다. 파이썬에서는 DP를 구현하는 방법은 여러가지가 있습니다. 여기서는 Memoization 방식과 Bottom-up 방식을 예제 코드로 설명하겠습니다. ​

Memoization 방식

​ Memoization은 이전에 계산한 값을 저장하고 재활용하는 방식입니다. 이전에 계산한 값이 필요할 때마다 값을 조회하여 사용합니다. Memoization 방식은 보통 재귀 함수와 함께 사용됩니다. ​ 아래는 Memoization 방식을 사용하여 피보나치 수열을 구하는 예제 코드입니다. ​

# Memoization 방식으로 구현한 피보나치 수열 예제
memo = [0] * 100  # 메모이제이션을 위한 리스트
​
def fibonacci(n):
    if n <= 1:
        return n
​
    if memo[n] != 0:  # 이미 계산한 값이라면 그 값을 리턴
        return memo[n]
​
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2)  # 계산한 값을 메모이제이션
    return memo[n]
​
# 피보나치 수열의 10번째 수 출력
print(fibonacci(10))

​ 위 코드에서 memo 리스트는 메모이제이션을 위한 리스트입니다. 이전에 계산한 값을 저장하기 위해 전역 변수로 선언되어 있습니다. fibonacci() 함수는 재귀 함수로, 피보나치 수열의 n번째 값을 계산합니다. ​ 먼저 n이 1보다 작거나 같은 경우에는 n을 그대로 리턴합니다. 이때, memo[n] 값이 0이 아니라면 이미 계산한 값이므로 그 값을 바로 리턴합니다. ​ 만약 memo[n] 값이 0이라면, 이전에 계산하지 않은 값이므로 memo[n]에 fibonacci(n-1)과 fibonacci(n-2)의 합을 저장한 후, memo[n] 값을 리턴합니다. ​

Bottom-up 방식

​ Bottom-up 방식은 작은 문제부터 해결하여 큰 문제를 해결하는 방식입니다. 보통 반복문을 사용하여 구현합니다. ​ 아래는 Bottom-up 방식으로 피보나치 수열을 구하는 예제 코드입니다. ​

# Bottom-up 방식으로 구현한 피보나치 수열 예제
n = 10  # 구하고자 하는 피보나치 수열의 크기
dp = [0] * (n + 1)  # DP를 위한 리스트
​
dp[0], dp[1] = 0, 1  # 초기값 설정
​
for i in range(2, n + 1):  # Bottom-up 방식으로 DP 계산
    dp[i] = dp[i - 1] + dp[i - 2]
​
# 피보나치 수열의 10번째