피보나치 수열

Konseo·2023년 8월 3일
0

알고리즘

목록 보기
2/21

개념

피보나치 수열

  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문 반복 횟수ab
    112
    223
    335
    458

    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)

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

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

    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)

profile
둔한 붓이 총명함을 이긴다

0개의 댓글