코드업 1916. (재귀함수) 피보나치 수열 (Large)

문제출처 

https://codeup.kr/problem.php?id=1916

(재귀함수) 피보나치 수열 (Large)

 

피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다.

첫 번째 수와 두 번째 수는 모두 11이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치 수열을 나열해 보면 다음과 같다.

 

1,1,2,3,5,8,13…1,1,2,3,5,8,13…

 

자연수 N을 입력받아 NN번째 피보나치 수를 출력하는 프로그램을 작성하시오.

단, N이 커질 수 있으므로 출력값에 10,009를 나눈 나머지를 출력한다.

※ 이 문제는 반드시 재귀함수를 이용하여 작성 해야한다.

 

입력

자연수 N이 입력된다. (N은 200보다 같거나 작다.)

 

출력

N번째 피보나치 수를 출력하되, 10,009를 나눈 나머지 값을 출력한다.

 

입력 예시  

7

출력 예시

13

 

 

 

문제풀이 

피보나치 수열 문제다. 재귀함수를 이용하여 풀어야 한다. 재귀함수로 풀면 시간초과로 문제가 풀리지 않았다.

자꾸 시간초과가 떠서 찾아보니 메모이제이션 을 사용해야 한다고 함.. 

 

듣도보도 못한 말..ㅠ 

 

메모이제이션이란 ?

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술

 

이라고 한다.

 

재귀함수 사용 시 호출이 계속되면 시간이 굉장히 오래걸리는 단점이 있기 때문에 반복수행 되는 동작을 따로

메모이제이션에 저장해주어 호출하는,,,?

재귀함수의 계속되는 호출을 단축시켜주고 재귀함수 사용 시 시간단축을 위한 방법이라 생각하면 될 듯 하다. 

 

 

피보나치 수열은 1번째, 2번째 값이 1 이다.

즉 3번째 값부터 쭉쭉쭉 f(n) = f(n-1)+f(n-2) 식이 성립된다.

memo = {1:1 , 2:1} # 메모이제이션에 값 저장 
 
def f(n):
    if n in memo: #n이 memo에 존재하면
        return memo[n] 
    else:
        output = f(n-1)+f(n-2) #memo에 존재하지 않으니까 두개를 더해준다.(1+1) 이 값을 output에 저장      
        memo[n] = output #memo의 n에 output값 저장
        return output
 
print(f(10)%10009) #출력값을 10009로 나누어 출력하라는 문제조건이 있었음