피보나치 수열 정리 (백준 2749 피보나치 수 3, 11444 피보나치 수 6)
1. 피보나치 수열이란? 피보나치 수열은 0번째, 1번째 항이 0, 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 피보나치 수열의 점화식을 세워 보자면 $ F_{n} = F_{n-1} + F_{n-2} (n>=2) $ 이다. 위의 식처럼 점화식이 무척 간단하기 때문에 N의 수가 작을 경우에는 동적 계획법을 통해 피보나치 수를 구할 수 있다. 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8,..
2020. 4. 28.