[백준] 2748번 피보나치 수 2 - Python

문제

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

출력 

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

예제 입력 1

10

예제 출력 1

55

 

---

나의 첫 풀이

# 사용자 입력
n = int(input())

# 함수 구현
def fibo(n):
    if n == 0 or n == 1: 
        return n
    else:
        return fibo(n-2) + fibo(n-1) 

# 함수 실행 및 출력
print(fibo(n))

시간 초과가 발생했다. 시간 복잡도를 줄일 수 있는 방법을 고민해야 한다. → 시간 복잡도 O(2^n) 

 

---

정답 코드 1 (DP)

# 사용자 입력 받기. 문자열이니까 인트형으로 변환
n = int(input())

# 피보나치 수 저장할 리스트 만들기 
fibo = []

# 피보나치 수가 0일때와 1일때 값 미리 저장해두기 
fibo.append(0)
fibo.append(1)

# 반복문을 돌면서 피보나치 수 계산하기 
for i in range(2, n+1): # n까지 하면 n-1까지 도니까 +1 해주기
    fibo.append(fibo[i-1]+fibo[i-2]) # 계산한 값을 계속 리스트에 저장하기 

# 결과값 출력
print(fibo[n])

시간 복잡도 O(n) 이다. 정답으로 인정은 됐지만 공간 복잡도도 줄일 수 있는 방법을 생각해보자. 

정답 코드 2 (queue)

# 사용자 입력 받고 문자열이니까 인트형으로 변환 
n = int(input())

# 큐를 사용할거니까 불러오기
from collections import deque

# 함수 정의하기 
def fibo_queue(n):

    # 큐에 미리 0번째, 1번쨰 피보나치 수열 값 넣어주기
    queue = deque([0, 1])

    # 입력받은 숫자가 1보다 작거나 같으면 그대로 반환
    if n <= 1:
        return n 
    
    # 2부터 N+1번 돌면서 큐에 피보나치 수열의 합 저장해주기 
    for _ in range(2, n+1):
        queue.append(queue[0] + queue[1])
        queue.popleft() # deque의 맨 앞쪽, 가장 왼쪽 요소를 제거. 그래야 큐에는 항상 0번쨰와 1번째만 남음

    return queue[-1] #큐의 마지막 요소가 피보나치 수열의 최종 합

print(fibo_queue(n))

큐를 활용한 방법이다. 공간 복잡도 O(1), 시간 복잡도 O(n)이다.  

정답 코드 3 (list 길이 2로 고정) 

# 사용자 입력 받고 문자열이니까 인트형으로 변환
n = int(input())

# 함수 정의
def fibo_list(n):
    if n <= 1:
        return n 
    
    # 리스트 초기화
    fibo = [0, 1]

    # 피보나지 수열 계산 (리스트의 길이 2로 고정)
    for _ in range(2, n+1):
        fibo[0], fibo[1] = fibo[1], fibo[0] + fibo[1]
    
    # 결과 반환
    return fibo[1]

print(fibo_list(n))

공간 복잡도 O(1), 시간 복잡 O(n)인 또 다른 방법이다.