[BOJ][Python]1003: 피보나치 함수

문제 정의

이 문제는 피보나치 수열을 재귀적으로 계산하는 함수를 구현하는 문제이다.

재귀 함수만을 이용하여 문제를 풀었을 경우 시간 제한이 있기에 풀 수 없다.

그렇기에 메모이제이션 기법을 통해 문제를 풀었다.

 

메모이제이션 

• 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하는 다이나믹 프로그래밍

 

# 테스트 케이스 개수
T = int(input())

# 메모이제이션을 위한 리스트
memo = [[0, 0] for _ in range(41)]
memo[0], memo[1] = [1, 0], [0, 1]

# 피보나치 수열을 계산하는 함수
def fibonacci(n):
    # 이미 계산된 값이면 메모이제이션된 값을 반환
    if memo[n] != [0, 0]:
        return memo[n]
    
    # 메모이제이션을 위해 이전 값들을 가져옴
    memo[n-1] = fibonacci(n-1)
    memo[n-2] = fibonacci(n-2)
    
    # n번째 값을 계산하고 메모이제이션
    memo[n] = [memo[n-1][0] + memo[n-2][0], memo[n-1][1] + memo[n-2][1]]
    return memo[n]

# 각 테스트 케이스마다 결과 출력
for _ in range(T):
    n = int(input())
    result = fibonacci(n)
    print(result[0], result[1])