[Algorithm] [Python & Swift] 백준/BOJ - 2748 _ 피보나치 수2

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

 

출력

---

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

 

제출 코드

---

Python

 

1차 제출 코드

def fibo(n):
    if n==1 or n==2:
        return 1
    return fibo(n-1) + fibo(n-2)

2차 제출 코드

from sys import stdin

n = int(stdin.readline())
cache = []

for i in range(n):
    if i < 2:
        cache.append(1)
    else:
        cache.append(cache[i-1] + cache[i-2])

print(cache[n-1])

 

Swift

import Foundation

var cache = [Int]()

var n = Int(readLine()!)!

for i in 0..<n {
    if i < 2 {
        cache.append(1)
    } else {
        cache.append(cache[i-1] + cache[i-2])
    }
}

print(cache[n-1])

 

문제 풀이

---

처음에는 단순 재귀를 이용하여 접근했다.

시간초과가 발생해서 DP 를 이용한 방법으로 접근했더니 간단히 풀렸다.

DP 루틴은 아래와 같다.

1. 메모이제이션을 위한 변수 생성. (관례적으로 dp, cache 등의 이름이 붙는다고 한다.)
2. 입력받은 정수까지 반복문을 진행한다.
3. 반복문 인덱스 값에 대응되는 피보나치 값을 계산하여 cache에 저장한다.
4. 이를 반복한다.

재귀와의 가장 큰 차이는 구한 값을 또 구하지 않는다는 것이다.

예를 들어, 재귀를 이용한 피보나치 수열은 아래와 같이 함수 콜스택이 호출된다.

• fibo(4)
  • ( fibo(3) + fibo (2) )
  • ( fibo(2) + fibo(1) ) + ( fibo(1) + fibo(0) )

위 코드만 봐도 fibo 함수에 전달되는 인자가 계속하여 반복되는 것을 살펴볼 수 있다.

입력값이 4임에도 불구하고 매우 겹치게 된다. 만일 입력값이 커진다면 수행하는데 드는 시간 비용도 기하적으로 커진다.

DP를 이용하면 위 단점을 커버할 수 있다.

DP의 핵심 개념은 메모이제이션, 한 번 계산한 값은 기록해놨다가 필요시 다시 계산하지 않고 캐시해와서 사용한다는 것이다.

따라서, 불필요한 계산을 줄여 보다 빠르게 작업을 수행할 수 있다.