[백준 10870번-파이썬/Python] 피보나치 수 5

http://acmicpc.net/problem/10870

 

{코드}

def fibo(n):
	if n < 2:
		return n
	else:
		return fibo(n-1) + fibo(n-2)
print(fibo(int(input())))

{설명}

피보나치 수열은 0과 1로 시작하며 바로 앞의 두 수를 더한 값이 다음 피보나치 수가 되는 수열입니다.

그렇기에 n번째 피보나치 수는 n-1번째와 n-2번째 수의 합이 되므로 위와 같이 구성됩니다.

만약 4번째 피보나치 수를 구한다고 하면 아래와 같이 구성됩니다. (무시하고 더 내리셔도 됩니다.)

1. n = 4
2. 4는 2 보다 작지 않음
   1. 3번째 피보나치 수를 찾음
      1. 3은 2보다 작지 않음
         1. 2번째 피보나치 수를 찾음
            1. 2는 2보다 작지 않음
               1. 1번째 피보나치 수를 찾음
                  1. 1은 2보다 작음
                  2. 1 반환
               2. 0번째 피보나치 수를 찾음
                  
                  1. 0은 2보다 작음
                  2. 0 반환
            2. 1 + 0인 1 반환 - 2번째 피보나치 수 = 1
         2. 1번째 피보나치 수를 찾음
            1. 1은 2보다 작음
            2. 1 반환
      2. 1 + 1 반환 - 3번째 피보나치 수 2
   2. 2번째 피보나치 수를 찾음
      1. 2는 2보다 작지 않음
         1. 1번째 피보나치 수를 찾음
            1. 1은 2보다 작음
            2. 1 반환
         2. 0번째 피보나치 수를 찾음
            
            1. 0은 2보다 작음
            2. 0 반환
      2. 1 + 0인 1 반환 - 2번째 피보나치 수 = 1
   3. 2 + 1 반환 - 4번째 피보나치 수 = 3

보시다시피 굉장히 길고 반복적인 작업이 많습니다.

2번째 수를 찾는 작업만 해도 함수 호출이 두 번인데 이걸 또 두 번 반복합니다.

만약 숫자가 커진다면 이렇게 함수 호출이 너무 많아져 스택오버플로우가 일어납니다.

이렇게 비효율적인 코드 대신에 동적계획법이라는 방식이 있습니다. 

 

 

{코드}

dp = [0, 1]
def dp_fibo(n):
	if n < len(dp):
		return dp[n]
	else:
		tmp = dp_fibo(n-1) + dp_fibo(n-2)
		dp.append(tmp)
		return tmp
print(dp_fibo(int(input())))

{설명}

이 글에서는 동적계획법에 대해 자세히 설명하진 않지만 꼭 공부하는 걸 추천드립니다.

동적계획법은 간단히 말하면 어떤 문제를 더 작은 문제로 나눈 다음, 이 작은 문제들의 답을 통해 큰 문제를 푸는 방식입니다.

그렇기에 같은 작업을 반복하는 피보나치 수열과 같은 문제를 해결하는데 효과적입니다.

위 코드는 만약 n번째 수가 저장되어 있지 않다면, 그 해를 찾아서 저장공간에 넣는 방식입니다.

다시 n이 4일때를 가정하면

1. n = 4
2. 4는 dp의 길이인 2보다 작지 않음
   1. 3번째를 구함
      
      1. 3은 dp의 길이인 2보다 작지 않음
         1. 2번째를 구함
            1. 2는 dp의 길이인 2보다 작지 않음
               1. 1번째를 구함
                  1. 1은 dp의 길이인 2보다 작음
                  2. dp[1]인 1 반환
               2. 0번째를 구함
                  1. 0은 dp의 길이인 2보다 작음
                  2. dp[0]인 0 반환
            2. dp에 1+0인 1 추가
            3. 1 반환
         2. 1번째를 구함
            1. 1은 dp의 길이인 3보다 작음
            2. dp[1]인 1 반환
      2. dp에 1+1인 2 추가
      3. 2 반환
   2. 2번째를 구함
   1. 2는 dp의 길이인 3보다 작음
   2. dp[2]인 1 반환
3. dp에 2+1인 3 추가
4. 3 반환

보기와 같이 2번째를 구하는 과정이 생략되었다는 것을 볼 수 있습니다.

또한, 파이썬과 반복문을 잘 활용하여 풀 수도 있습니다.

{코드}

cur, next = 0, 1
for _ in range(int(input())):
	cur, next = next, next + cur
print(cur)

{설명}

피보나치 수열은 전의 두 개의 수의 합이 새로운 수가 되기 때문에 그 두 개의 수를 계속해서 더하는 방식으로 풀 수 있습니다.

만약 n이 4라면

4번 동안 반복문이 돌며 

1. 첫 번째 - cur = 1, next = 1 + 0
2. 두 번째 - cur = 1, next = 1 + 1
3. 세 번째 - cur = 2, next = 2 + 1
4. 네 번째 - cur = 3, next = 3 + 2

결국 cur인 3을 출력합니다.

여기서 3번째에 이미 next가 3이지만 n이 0이라면 답이 나오지 않기에 한번 더 반복합니다.

*이건 재미로 보세요

피보나치 수열은 반복문이나 재귀 함수로 풀 수도 있지만 식을 통해 한번에 풀 수도 있습니다. (검색창에 '피보나치 수열 일반항'을 검색해보세요.)

from math import sqrt
def fibo(n): 
    phi = (1 + sqrt(5)) / 2
    return round(pow(phi, n) / sqrt(5)) 
print(fibo(int(input())))