본문으로 건너뛰기
실습하기

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

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


1. 함수 정의 및 메모이제이션 구조 설정​

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

메모이제이션 구조 설정 예시
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]

2. 재귀 호출 및 결과 저장​

함수는 피보나치 수열의 (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]

알고리즘 복잡도​

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

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

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

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

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!