[알고리즘/재귀호출/Python] 백준 2747 - 피보나치 수

문제 : 2747번: 피보나치 수 (acmicpc.net)

2747번: 피보나치 수

 

사용언어 : Python 3

 

시간제한 : 1초

메모리 제한 : 128 MB

 

문제 설명

 n 번째 피보나치 수를 구하는 문제이다. 피보나치 수의 0과 1번째 피보나치 수는 각각 0과 1이다. 이후 n번째(n>1) 피보나치 수는 바로 앞 두 피보나치 수의 합이 된다.

 

$F_{n} = F_{n-1} + F_{n-2}$ (n > 1)

 

입력

 첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

 

예제 입력

10

 

출력

 첫째 줄에 n번째 피보나치 수를 출력한다.

 

예제 출력

55

 

사용된 알고리즘 : 재귀 호출(recursive call)

 재귀 호출(recursive call)이란 특정 함수에서 자기 자신을 호출하는 것을 뜻 한다. 재귀 호출을 사용할 때 주의해야 할 점은 무한히 반복되지 않도록 중단을 위한 명령문을 반드시 포함해야 한다는 것이다.

 

 재귀 호출로 5번째 피보나치 수를 구한다면 연산 과정은 아래와 같은 형태를 띄게 된다. 

재귀호출을 통한 5번째 피보나치 수 연산과정

 피보나치 수를 구하기 위해선 바로 앞 두 피보나치 수열을 구하는 연산을 다시 수행해야한다. n번째 피보나치 수를 구하기 위한 시간복잡도는 O($2^{n}$)이다. n이 커질 수록 필요한 연산은 기하급수적으로 증가하게 된다. 

 

 재귀 호출을 통하여 해결한 코드는 아래와 같다. 하지만 n이 클 때 연산을 수행하는 시간이 매우 크기 때문에 시간내에 문제를 해결할 수 없다.

def fibonacci(n):
  if n == 0:
    p[0] = 0
    return 0
  if n == 1:
    p[1] = 1
    return 1
  if p[n] == 0:
    p[n] = fibonacci(n-1) + fibonacci(n-2)
  return p[n]
  
p = [0] * 46
print(fibonacci(int(input())))

 

따라서 제한시간 내에 문제를 해결하기 위해서는 다른 방식의 풀이가 필요하다. 동적계획법과 단순히 반복문을 사용한 방식 등 여러 방법이 존재하지만 본 게시글에선 단순한 반복문을 통해 문제를 해결하였다. 반복문을 통한 답안 코드는 아래와 같다.

n = int(input())

a, b = 0, 1

for i in range(n):
  a, b = b, a + b

print(a)