[코드업] 1916 : (재귀함수) 피보나치 수열 (Large) 파이썬

문제출처 https://codeup.kr/problem.php?id=1916

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

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

 

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

 

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

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

※ 이 문제는 반드시 재귀함수를 이용하여 작성 해야한다. 금지 키워드 : while goto for

 

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

 

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

 

---

[코드업] 1916 : (재귀함수) 피보나치 수열 (Large) 파이썬

 

재귀함수에 들어와서 풀어본 간단한 코드로는 N번째가 200까지 받아 계산하기는 매우매우 느려진다.

n에 30 넘어가도 느릿느릿. 이것은 재귀로 들어가면서 했던 계산을 또 계산하고 했던 계산을 또 계산하기 때문.

피보나치 수열의 확장판! 메모이제이션을 이용해보자 

메모이제이션 : 처음 계산한건 기록하고, 계산하기 전에 계산해둔게 있으면 써먹기  

 

<PASS> 일단..

# 내 첫 메모이제이션...
#  메모이제이션 이용하기
fibo = [0]*201 # 인덱스 번호가 피보나치의 자릿수 [0 1 1 2 3 5 ...]
fibo[1] = 1 # 초기화 [0,1,0...]
 
 
def fast_f(n):
    if n == 0 or n == 1:
        return n
    if fibo[n] == 0:
        fibo[n] = fast_f(n - 1)+ fast_f(n - 2)
    return fibo[n]
 
 
def fibonacci(n):
    if n == 1:
        return n
    return fast_f(n)
 
n = int(input()) # 200이하 자연수
print(fibonacci(n)%10009)
 
 

 

<모범코드>

 
memo={1:1,2:1}
 
def f(x) :
    if x in memo :
        return memo[x]
    memo[x]=(f(x-1)+f(x-2))%10009
    return memo[x]
 
n=int(input())
print(f(n))
 

 

우와. 이걸 보고 다시 보니 얼마나 불필요 동작을 많이 했는지 배우게 된다 ... 이거지... 크bb

 

 

<개선>

초기값에 따라 약간의 차이가 있을 수 있다.  위에 코드에서 쓸모없는걸 치다 보니 이렇게 되었다.

# # (1)
fibo = [0]*201 # 인덱스 번호가 피보나치의 자릿수 [0 1 1 2 3 5 ...] 입력값 자연수가 200이라 함
#fibo[1] = 1 # 초기화 [0,1,0...]
 
def fast_f(n):
    if n < 2: # n==0 일때는 0 , n==1 일때는 1
        return n
    if fibo[n] == 0:
        fibo[n] = (fast_f(n - 1) + fast_f(n - 2))%10009
    return fibo[n]
 
n = int(input()) # 200이하 자연수
print(fast_f(n)) # 그냥 결과값이 길어서 나머지값 구하라 한거... # 5227
print(fibo)
 
 
# # (2)
fibo = [0]*201
fibo[1] = 1 # 초기화 [0,1,0...]
 
def fast_f(n):
    if n < 1: # n==0 일 때는 0 
        return n
    if fibo[n] == 0: # n==1 일때는 이부분이 넘어가고 fibo[1] = 1 이 리턴됨
        fibo[n] = (fast_f(n - 1) + fast_f(n - 2))%10009
    return fibo[n]
 
n = int(input()) # 200이하 자연수
print(fast_f(n)) # 그냥 결과값이 길어서 나머지값 구하라 한거... # 5227
print(fibo)
 
 

---

기본 피보나치 재귀 코드

 

 
# n번째 피보나치 수를 리턴 0 1 1 2 
def fib(n):
    # 초기값 1
    if n == 0:
        return 0
    if n == 1:
        return 1
 
    # 초기값 2
    if n < 3: # n == 1 or n == 2 일때 1이다.
        return 1  
 
    return fib(n-1)+fib(n-2)
    
 
# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
    print(fib(i))
 

 

#1 . 재귀. 기본, 범위넘으면 시간초과
def fibo(n):
    if n == 1 or n ==2 :
        return 1
    return fibo(n-1)+fibo(n-2)
 
N = int(input())
print(fibo(N))
 
# 2. while
def fib(n):
  i, a, b = 0, 0, 1
  while i < n:
    a, b, i = b, a + b, i + 1
  return a
x = int(input())
print(fib(x))
 
# 3. for loop
def fibonacci(n):
  current, next = 0, 1
  for i in range(n):
      current, next = next, current + next
  return current