BAEKJOON 2748
문제
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597. n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.
들어가기에 앞서
모두 다 알다싶이 기존의 “피보나치” 문제를 생각하면 다음과 같은 재귀를 생각할것이다.
def fivo(n): if n == 0: return 0 if n == 1: return 1 return fivo(n-1) + fivo(n-2)그러나 이 재귀함수의 피보나치 구현은 한 가지 큰 문제점을 가지고 있다. 5번쨰를 구하기위해서 했던 작업들을, 6번째를 구하기 위해서 다시 5번째까지 했던 작업들을 또 해야한다. 만일 우리가 5번째까지 했던 작업들을 가지고 있다면, 6번째를 구할 때 중복된 작업 없이 더 빠르고 효율적으로 구할 수 있을 것이다.
이와 같은 작업을 동적 계획법, (=다이나믹 프로그래밍)을 통해서 구현을 할 수가 있다.동적 계획법 이란, 분할 정복 알고리즘과 비슷하다. 주어진 문제를 부분 문제로 나누어 각 부분문제의 답을 계산하고, 이 계산한 결과값을 이용해서 원하고자 하는 문제의 답을 얻으면 된다. 여기서 분할정복과 다른점은, 동적계획법은 부분 문제들을 최대한 많이 이용하도록 나누고, 이것들을 저장한뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 이용해 더욱 효율적으로 구할 수 있는 것이다.
나의 처음 코드
위에서 설명한 것처럼 그전의 정보들을 저장해서 더욱 빠르게 피보나치 함수를 구하도록 구현을 해봤다. dp_list가 기존의 정보(=부분 문제)를 저장해두는 리스트라고 생각하면 된다. 그러면, 재귀 없이 더욱 빠르게 구할 수 있다.
n = int(input())
dp_list = []
def get_fibo(nth : int):
if nth == 0:
dp_list.append(0)
if nth == 1:
dp_list.append(1)
#찾고자 하는 정보가 dp_list안에 있을 때
if len(dp_list) == nth+1:
return dp_list[nth]
else:
dp_list.append(dp_list[nth-1] + dp_list[nth-2])
for i in range(n+1):
get_fibo(i)
print(dp_list[-1])
결과는 맞았습니다. 그러나 코드가 생각보다 파이썬스럽지 못해서 다시 한번 리팩토링 해보았다. 그 코드는 다음과 같다.
n = int(input())
fibo = [0, 1] + [0] * 90
for i in range(2, n+1):
fibo[i] = fibo[i-2] + fibo[i-1]
print(fibo[n])
결과는 맞았습니다. 조금 더 간결해서 보기가 훨씬 수월하다. 다음에 다룰 문제도 피보나치 문제이다. 포스팅(1003)을 참고하면 도움이 될 것이다.