동적 계획법 파이썬 구현 방법

부분 문제의 결과를 저장하고 재사용하는 동적 계획법을 파이썬 코드로 살펴보겠습니다.

동적 계획법은 계산 결과를 저장하고 재사용하는 방법입니다. 이를 위해 메모이제이션을 사용합니다.

Copy
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n] # 메모이제이션
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

함수는 피보나치 수열의 (n)번째 값을 계산하고, 이를 memo에 저장합니다. 이렇게 저장된 값은 재사용됩니다.

Copy
if n in memo:
    return memo[n]
if n <= 2:
    return 1
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]

1. 시간 복잡도 (Time Complexity): O(n)

   • 메모이제이션을 사용하는 피보나치 함수의 시간 복잡도는 O(n)입니다. 각 숫자에 대한 피보나치 값은 한 번만 계산되며, 계산된 값은 저장되어 재사용됩니다.

2. 공간 복잡도 (Space Complexity): O(n)

   • 메모이제이션을 위해 사용되는 추가 메모리 공간으로 인해 공간 복잡도도 O(n)입니다. 각 계산된 피보나치 수는 memo 사전에 저장되므로, n번째 수를 계산하기 위해 최대 n개의 공간이 필요합니다.