N번째 피보나치 수를 구하는 문제입니다. 10870번: 피보나치 수 5에서는 재귀 함수를 이용하여 구했지만, 이 알고리즘의 시간 복잡도는 \(O(\phi^n)(\phi=\frac{\sqrt{5}+1}{2}\simeq1.618)\)로 알려져있어 비효율적인 알고리즘입니다. 이 문제는 이보다 빠른 O(n)의 시간복잡도를 사용하는 동적 계획법을 이용하여 풀어야 합니다. 피보나치 수를 저장할 배열을 선언한 후, 2번째 피보나치 수부터 차례로 구하되(0번째, 1번째는 정의되어있습니다), 이미 구한 적이 있는 피보나치 수는 배열에서 꺼내쓰도록 하는 것이죠. 그러면 각 피보나치 수를 구할 때 O(1)의 시간복잡도로 구할 수 있게 됩니다. 이걸 N번째 피보나치 수를 구할 때까지 반복하므로 O(n)으로 처리가 가능합니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-31 13:26:17 |