문제
fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
fibonacci(0)은 0을 출력하고, 0을 리턴한다.
fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
//입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
//출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
정답코드
import sys
T=int(sys.stdin.readline())
# 0,1의 출력횟수를 저장하는 리스트 2개 생성, 초기값
# N은 최대 40이므로 40번 인덱스까지 필요하다
d=[0]*41
d[0],d[2]=1,1
d1=[0]*41
d1[1],d1[2]=1,1
# 0,1의 개수도 피보나치 수열대로 증가
for i in range(3,41):
d[i]=d[i-2]+d[i-1]
d1[i]=d1[i-2]+d1[i-1]
for v in range(T):
n=int(sys.stdin.readline())
print(d[n],d1[n])
일반적인 피보나치로 풀게 되면 예제에 있는 22정도는 바로 출력이 됐는데 입력값이 30만 해도 0 출력은 50만, 1 출력은 80만이 넘어버려서 시간초과로 틀리게 된다
틀린 코드 일부
def fibo(n):
if n==0:
d[0]+=1
return 0
elif n==1:
d[1]+=1
return 1
else:
return fibo(n-2)+fibo(n-1)이렇게 코드를 짰다. d만 넣는다고 다이나믹 프로그래밍이 아니었다는걸 이번 기회에 확실히 알았다. 저게 전형적인 피보나치 였다.
시간복잡도
재귀함수를 통해 구현한 피보나치 수열의 시간복잡도는 O(N^2) 이라고 한다. 따라서 이러한 문제에서는 반드시 메모이제이션을 사용해야 한다.
메모이제이션을 이용하면 필요한 값을 매번 계산하지 않고 리스트에 저장해 두었다가 불러와 계산하게 되므로 시간복잡도가 O(N)으로 줄게 된다.
