[Dynamic Programing] 피보나치 수열 공간 최적화

실습 설명

공간최적화 관점으로 본다면, n번째 피보나치 수를 계산하기 위해서는 가장 최근에 계산한 두 값만 알면 됩니다.
 
공간 복잡도 O(1)로 fib_optimized 함수를 작성하세요.

print(fib_optimized(1))    # 1을 출력
print(fib_optimized(2))    # 1을 출력
print(fib_optimized(3))    # 2을 출력
print(fib_optimized(4))    # 3을 출력
print(fib_optimized(5))    # 5을 출력

 

def fib_optimized(n):
    # 여기에 코드를 작성하세요
    curent = 1
    previous = 0
    
    if n > 1:
        for i in range(1, n):
            temp = curent
            curent = curent + previous
            previous = temp
            
        return curent
    
    return curent


# 테스트 코드
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))

해결과정
curent와 previous를 업데이트 할때, 

temp = current
current = current + previous
previous = temp

이렇게 했지만, 
효율을 위해 python에 먼저 튜플을 만들고 튜플을 unpack하는 스킬(?)을 알게되었다.

current, previous = current + previous, current

이렇게 하면 임시 저장 변수 없이, 한 줄에 작성할 수 있다.
 

출처 코드잇