[알고리즘] Dynamic Programming 공간최적화 : 피보나치 수열

Dynamic Programming을 할때, 모든 계산 값을 저장할 필요가 없다면 공간 사용을 최적화 한다.

Tabulation은 모든 값을 리스트에 저장하고 있으므로 비효율적이다. 

r가장최근 값 current 직전 값 previous 을 활용한다.(사용하는 메모리는 늘어나지 않음)

 

실습설명

영상에서 보듯, 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을 출력

힌트1

영상에서 본 것처럼 필요한 변수를 정의하세요. 영상에서 변수 current와 변수 previous를 사용합니다.

 

힌트 2

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

반복문은 어떻게 작성할 수 있을까요? 우선 반복문을 몇번 돌아야 하는지 생각해 봅시다.

n이 1이면 반복문을 몇번 돌아야하나요? n이 2면? n이 3이면?

 

힌트3

이미 current는 1이기 때문에, n이 1이면 반복이 필요없습니다. n이 2면 반복문을 한번 실행해야 하고, n이 3이면 반복문을 두 번 돌면 됩니다.

 

힌트4

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

    # 반복적으로 위 변수들을 업데이트한다. 
    for i in range(1, n):

이제 반복적으로 current와 previous를 업데이트 하면 되는데 어떤 방식으로 할 수 있을까요?

 

힌트5

current와 previous를이렇게업데이트 할 수 있습니다.

temp = current
current = current + previous
previous = temp

보다시피 temp라는 임시 저장 변수를 활용했는데. 사실 파이썬에서는 이 세줄을 한줄로 줄일 수 있습니다. 혹시 아시나요?

 

힌트6

current, previous = current + previous, current

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

 

답안

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

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

    # n번재 피보나치 수를 리턴한다. 
    return current


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