[BOJ] 1003번 피보나치 함수 / 사용언어 : 파이썬(python)

※ 문제링크 

1003번: 피보나치 함수

※ 관련개념

메모이제이션 - 위키백과, 우리 모두의 백과사전

해당문제는 피보나치 함수의 성질을 이용하여 0와 1의 호출횟수를 출력하는 문제였다. 단순하게 피보나치 함수를 재귀함수로 구현하게 되면 시간초과가 발생할 것 같아 동적계획법 중 하나인 메모이제이션을 활용하기로 하였다. 간단하게 메모이제이션에 대해 설명하면 특정 함수의 출력값을 딕셔너리에 저장하여 다음에 사용할 때에는 재귀함수를 돌리는 것이 아닌 딕셔너리에서 꺼내서 쓰는 방법이라고 생각하면 되겠다. 자세한 풀이 방법과 코드는 아래와 같다.

1. 피보나치 함수의 호출횟수를 카운트할 함수와 그 값들을 저장할 딕셔너리를 만든다.

2. 입력값과 출력값을 보여줄 코드를 작성한다.

+ 만약 처음에 N이 10이었다면, 딕셔너리에는 0~10까지의 값들이 모두 저장된다. 그 이후 10이하의 수로 출력하게되면

   딕셔너리에 있는 값들 참조해서 사용하게 되며, 이로 인해 시간과 메모리의 절약이 되는 것이다.

 

fibonacci_zo_memo = {}
def fibonacci_zo(number):
    if number == 0:
        fibonacci_zo_memo[number] = [1, 0]
    elif number == 1:
        fibonacci_zo_memo[number] = [0, 1]
    if number not in fibonacci_zo_memo:
        s1 = fibonacci_zo(number-1)
        s2 = fibonacci_zo(number-2)
        fibonacci_zo_memo[number] = [s1[0] + s2[0], s1[1] + s2[1]]
    return fibonacci_zo_memo[number]


import sys
T = int(input())
for _ in range(T):
    N = int(input())
    print(*fibonacci_zo(N))

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.