[알고리즘/재귀호출/Python] 백준 2747 - 피보나치 수
문제 : 2747번: 피보나치 수 (acmicpc.net)
사용언어 : 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번째 피보나치 수를 구한다면 연산 과정은 아래와 같은 형태를 띄게 된다.
피보나치 수를 구하기 위해선 바로 앞 두 피보나치 수열을 구하는 연산을 다시 수행해야한다. 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)