백준 1003번 피보나치 함수

백준 1003번은 기초적인 동적 계획법(DP, Dynamic programming) 문제입니다. 시간제한이 0.25초로 매우 빡빡한 편이라서 시간복잡도 O(n)으로 풀어야 해결 가능합니다. 다음 소스는 문제에서 주어진 $N$번째 피보나치 수를 구하는 C++ 함수입니다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } 이와같이 재귀적으로 N번째 피보나치 숫자를 구했을때 0과 1이 각각 몇번씩 return되는지 구하는 문제인데, $fib(n)$ 을 $n$번째 피보나치 숫자를 반환..

2020.01.15