[백준] 2748 피보나치2 Python

1. 문제

n 이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오 
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), 0 <= 90

 

2. 알고리즘 분류

* 수학

* 다이나믹 프로그래밍

 

3. 접근 방식

n 이 90까지라서 재귀로 풀면 시간 초과가 뜬다는 말을 듣고,

어제 공부했던 Dynamic Programming 의 메모이제이션을 활용하여 구현해 보았다

메모이제이션 - 이전 결과 값을 저장하여 중복 계산을 피하는 것 

 

4. 코드 구현 

def fibo(n):
    if n <= 1: # 기저 설정 
        return n 
    
    list = [0] * (n+1) # 결과 리스트 선언 및 초기화 
    list[1] = 1 # 피보나치 수열에서 첫번째 값은 1

    # 메모이제이션으로 피보나치 함수 구현 
    for i in range(2, n+1): # 2부터 n까지 반복
        # fibo[n] = fibo[n-1] + fibo[n-2]
        list[i] = list[i-1] + list[i-2]
    result = list[n] # 마지막 계산 결과를 result 에 저장 

    return result

if __name__ == '__main__':
    n = int(input()) # n 입력 받기 

    print(fibo(n)) # 결과값 출력