[백준] 2747번 : 피보나치 수

유형 : 재귀 함수

[예제]

10

[출력]

55

---

1. 내 풀이

n = int(input())
_list = [0,1]
for i in range(n):
    _list.append(_list[i]+_list[i+1])

print(_list[n])

▷ 피보나치 수의 식인 Fn = Fn-1 + Fn-2 (n ≥ 2)을 이용해서 풀었다.
▷ 처음 두 수 0,1을 리스트에 받고, 이 리스트를 이용하였다.

▷ 문제에서 전체 배열이 아니라 n번째 피보나치 수를 출력하라고 했으니, 굳이 append로 할 필요는 없어 보인다.

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

** 핵심 아이디어
1. 피보나치 수열의 점화식을 세움
   F0 = 0, F1 = 1
   Fn = Fn-1+ Fn-2 (n ≥ 2)
2. 재귀 함수를 이용해 문제를 풀 수 있는지 검토
3. 문제에서 N은 최대 45

 

1) 재귀적 구현

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
    	return 1
    return fibonacci(n-1) + fibonaci(n-2)
    
print(fibonacci(int(input())))

▷ 이 경우 시간 초과 발생 → 시간복잡도 : O(2ⁿ)

▷ 아래 그림을 보면 f(3)을 구하기 위해, f(2), f(1)을 구한 다음 합을 구해야 한다. 구해야 하는 피보나치 수가 커지면 그에 따라 계산이 많아지기 때문에(동일한 수를 또 계산/호출해야 하는 문제) 재귀적 구현의 한계를 알 수 있다.

2) 반복문 구현

n = int(input())

a,b = 0,1

while n > 0:
    a,b = b, a+b
    n -= 1
    
print(a)

 

 

문제 출처 : https://www.acmicpc.net/problem/2747

2747번: 피보나치 수