피보나치 수열

개념

피보나치 수열

1. 피보나치 수열은 n번째 값이 (n-2)번째 값과 (n-1)번째 값을 더한 값임을 만족하는 수열임
2. 즉, 1, 1, 2(1+1), 3(1+2), 5(2+3), 8(3+5), 13(5+8), 21(8+13), 34(15+24), 55(21+34) …
3. 결국

코드로 구현하기

1. 일반 반복문 활용

   def fibonacci(n):
   	a,b=1,1
   	if n==1 or n==2:
   		return 1
   	for i in range(1,n):
   		a,b=b,a+b #swap
   	return a

   ex. 피보나치 수열의 5번째 값을 구하고자 할 때

   for문 반복 횟수	a	b
   1	1	2
   2	2	3
   3	3	5
   4	5	8

   4번째 반복 할 때의 a값

   즉, 5가 피보나치 수열의 5번째 값을 의미한다.

2. 재귀 함수

   def fibonacci(n)
   	# 피보나치 수열의 n번째 항들은 결국 1의 합들로 구성된것이라고 생각하면 쉬움
   	if n>=2:
   		fibonacci(n-2) + fibonacci(n-1)
   	elif n==1:
   		return 1
   	elif n==0:
   		return 0
   

   피보나치 수열의 특성 그대로 코드를 구현해주면 되기 때문에 너무 쉽게 재귀함수로 구현할 수 있다.

   그러나 재귀함수의 가장 큰 문제점은 효율성이 좋지 못하다는 점인데, 이미 계산되었던 값일지라도 의미 없이 다시 계산을 반복하기 때문이다.

   따라서 이와 같은 문제점을 해결하기 위해서는 동적계획법(dynamic programming,DP)에서 활용되는 메모이제이션(memoization)을 사용해야한다.

   핵심적인 것만 얘기하자면, DP에서는 큰 문제를 해결하기 위해 작은 문제들을 해결해나가야 하는데, 그 작은 문제들의 결과값은 변하지 않아야한다. 그리고 그 결과값이 변하지 않는 작은 문제들이 계속 반복해서 일어나게 된다.

   여기서 메모이제이션은 자꾸만 반복되지만 그 결과값은 변하지 않는 작은 문제들의 결과값을 저장하는 것을 의미한다. 이미 결과값이 기록된 작은 문제의 경우, 메모이제이션을 통해 값을 불러온다면 불필요한 계산을 대폭 감소시킬 수 있다.

   결국 재귀함수 또한 큰 문제를 해결하기 위해 탈출 조건을 만날 때까지 작은 문제들을 풀어나가야하는 행위이기 때문에, 그 과정 중에 결과값이 바뀌지 않는 작은 문제들이 존재할 수 있다.

   결론적으로, 피보나치의 n번째 수를 구하는 함수에 메모이제이션 개념을 도입하면 다음과 같이 코드를 구현 할 수 있다.

3. 메모이제이션(dp) + 재귀함수 활용

   dic = {} #memoization을 위한 dictionary를 함수 외부에 선언
   
   def fibonacci(n):
   	if n in dic:
   		return dic[n]
   	
   	if n==0:
   		dic[0]=0
   	elif n==1:
   		dic[1]=1
   	else:
   		dic[n]=fibonacci(n-1)+fibonacci(n-2)

   위 코드가 지저분해보인다면 n이 0과 1일 때의 값은 dictionary에 미리 넣어두어도 된다.

   fib={0:0,1:1}
   
   def fibonacci(n):
       if n in fib:
           return fib[n]
       fib[n]=fibonacci(n-2)+fibonacci(n-1)
       return fib[n] # return 까먹지 않기
   
   n = int(input())
   
   print(fibonacci(n)%1000000007)

   재귀함수의 효율성이 많이 떨어진다면, 메모이제이션을 활용하여 효율성을 증대시켜보자.

4. 메모이제이션 + 반복문 활용

   n = int(input())
    
   dp= [0,1,1] #여기서는 배열 선언
    
   for i in range(3,n+1):
       dp.append((dp[i-1]+dp[i-2])%1000000007)
    
   print(dp[n])

관련 문제

1. 백준 15642번 피보나치 수7
   1. 해당 문제에서 재귀로 피보나치를 구현하면 런타임에러(recursionError)가 발생한다. 왜그럴까?
   2. recursionError 원인
      • 대부분 재귀호출이 너무 깊어질 때 발생한다
        1. return 조건을 제대로 걸어주지 않아 depth가 매우 커진 경우
        2. return 조건을 제대로 걸어주었음에도, 애초에 python이 정한 최대 재귀 depth보다 구현한 재귀의 depth가 더 큰 경우
           • python의 sys.getrecursionlimit()를 통해 확인 가능하며, 백준 서버에서는 이를 1,000으로 제한하고 있음
   3. 해결방법

      1. 재귀 → 반복문으로 변환 (쉽게 해결)

      2. 최대 재귀 깊이 리밋 늘리기

         ex. sys.setrecursionlimit(10**6)