[백준 알고리즘] 10870번: 피보나치 수 5 (Python)

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

문제

피보나치 수는 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은 20보다 작거나 같은 자연수 또는 0이다.

 

출력

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

 

소스코드

재귀함수

 

 

반복문

 

 

풀이

★ 재귀로 푸는 방법과 반복문으로 푸는 방법의 차이는 시간 복잡도에서 나타납니다. 재귀는 함수가 호출된 부분에서 다시 함수로 돌아가는 과정을 반복하기 때문에 그만큼 시간이 많이 걸립니다. 하지만 반복문은 반복만 하면서 수를 더하기 때문에 비교적 시간이 덜 걸립니다.

 

★ 재귀: 매개변수로 들어오는 k가 0이나 1 또는 2가 아닐 때는 else문이 실행됩니다. 이때 else문에서 함수의 호출이 이루어지는데, 매개변수 k를 -1한 것에 -2한 것을 더한 값을 다시 리턴합니다. 이러한 과정을 계속해서 반복하게 되는데, 그 과정은 다음과 같습니다. 

 

입력 받는 k의 값이 크면 클수록 이러한 과정을 더 많이 반복해야 하기 때문에 시간이 많이 걸리게 됩니다. 

 

★ 반복문: 피보나치 수는 해당 수 바로 앞 두 수의 합이 됩니다. 그렇기에 변수를 2개 설정하고 해당 수 2번째 앞 수를 a로 잡고 1번째 앞 수를 b로 잡았을 때, 반복문을 돌면서 1번째 수가 2번째 수가 되고, 그 두 수의 합이 1번째 수가 되는 과정을 진행하면 됩니다. 

ex) n =7

a = 0

b= 1

for i in range(n):

    a,b = b, a+b

    return a 

 

=> i가 0일 때 a = 1, b = 1

=> i가 1일 때 a = 1, b = 2

=> i가 2일 때 a = 2, b = 3

=> i가 3일 때 a = 3, b = 5

=> i가 4일 때 a = 5, b = 8

=> i가 5일 때 a = 8, b = 13

=> i가 6일 때 a = 13, b = 21