C++ Algorithm/백준 알고리즘 문제 풀이
피보나치 수
3영2
2019. 3. 11. 14:44
반응형
2747번 문제 : 피보나치 수
https://www.acmicpc.net/problem/2747
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include <iostream> using namespace std; int Fibo(int n) { if (n < 0) return 0; else if (n == 0) return 0; else if (n == 1) return 1; else return Fibo(n - 1) + Fibo(n - 2); } int Fibo2(int n) { if (n < 0) return 0; else if (n == 0) return 0; else if (n == 1) return 1; else { int fib[1000] = { 0 }; fib[0] = 0; fib[1] = 1; for (int i = 2; i < 1000; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } return fib[n]; } } int Fib[50] = { 0 }; int Fibo3(int n) { if (n <= 2) return 1; if (Fib[n] != 0) return Fib[n]; else { Fib[n] = Fibo3(n - 1) + Fibo3(n - 2); return Fib[n]; } } int main() { int inp; cin >> inp; // cout << Fibo(inp); //Time Out // cout << Fibo2(inp); cout << Fibo3(inp); return 0; } | cs |
메모:
-3가지 방식으로 피보나치 수를 구할수 있다.
-첫번째 재귀방식으로 가장 직관적이나 효율성에 문제가 있음
-세번째 방법은 메모이제이션(Memoization) 방식
반응형