lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter3Title

pythonIntroAlgorithms2Chapter4Title

def fibonacci(n, memo={}):
    # 메모에 있으면
    if n in memo:
         # 메모된 값을 리턴
        return 0
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
    
print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))
print(fibonacci(5))
print(fibonacci(6))

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

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

<br />

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

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

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

<br />

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

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

```python title="재귀 호출 및 결과 저장 예시"
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]
```

<br />

## 알고리즘 복잡도

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

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

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

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