[파이썬] 피보나치 수열 (3) 공간 최적화 - 다이나믹 프로그래밍 ★

실습 설명

 n번째 피보나치 수를 계산하기 위해서는 가장 최근에 계산한 두 값만 알면 됩니다.

공간 복잡도 O(1)로 fib_optimized 함수를 작성하세요.

실습 결과

def fib_optimized(n):
    current = 1
    previous = 0

    # 반복적으로 위 변수들을 업데이트한다. 
    for i in range(1, n):
        print("%i : cur[%d], pre[%d]" %(i,current, previous))
        current, previous = current + previous, current

    # n번재 피보나치 수를 리턴한다. 
    return current
    
# 테스트 코드
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))

1 : cur[1], pre[0]
2 : cur[1], pre[1]
3 : cur[2], pre[1]
4 : cur[3], pre[2]
5 : cur[5], pre[3]
6 : cur[8], pre[5]
7 : cur[13], pre[8]
8 : cur[21], pre[13]
9 : cur[34], pre[21]
10 : cur[55], pre[34]
11 : cur[89], pre[55]
12 : cur[144], pre[89]
13 : cur[233], pre[144]
14 : cur[377], pre[233]
15 : cur[610], pre[377]

987
53316291173
146178119651438213260386312206974243796773058