1003번 : 피보나치 함수

 

시간 제한 걸려있음

문제에서 제공해준 피보나치 함수

• 이번에는 c++을 이용하여 피보나치 함수를 풀어봤다. 이 문제는 시간제한이 걸려있어서 처음에 너무 당황하였다. 왜냐하면 fibonacci 재귀 함수를 주고서 분석하라고 해서 재귀 함수를 써야 한다는 생각을 못 버렸다. 아래는 처음 풀이다. 
• 또한 각 0과 1의 출력횟수는 fibonacci(N-1) , fibonacci(N)이다. 

0과 1 출력 횟수

재귀를 이용한 풀이

위의 코드를 이용해서 풀었더니, 결과는 시간 초과.... , 그래서 어떻게 풀어야하나 고민을 하게 되었다.

그때, 알고리즘의 한 종류인 Dynamic Programming을 알게 되었다. 일명 dp.

• 위키피디아의 DP 정의

일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다.

 

위를 통해서 얻게 된 아이디어! dp라는 이중 배열을 만들어서 미리 앞의 연산 값을 저장해 놓는다!!!

 

dp 배열 선언 및 초기값 저장

i = 2를 위에서 선언해 놓고 증가 시키므로, 각 n마다 앞의 연산을 할 필요가 없어 진다.

 

---

• DP를 사용하여서 fibonacci 재귀 함수를 사용할 필요가 없어졌다. 그래서 시간 초과의 문제를 해결하였다.
•