[Leetcode] 509번 - 피보나치 수열
1. 문제 파악문제 링크: https://leetcode.com/problems/fibonacci-number/description/문제 요구사항: 피보나치 수열을 구현해라.시간복잡도: 입력 크기가 30개이므로 (2^10)^3=1,024^3≈(10^3)^3≈10^9이다. 따라서 10^8을 초과하므로 통과를 못할수도 있다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출피보나치 수열은 특정 숫자를 구하기 위해서 그 한칸 앞에 있는 값과 두칸 앞에 있는 값을 더해야한다. 따라서 피보나치 수열의 점화식은 f[i] = f[i-1] + f[i-2]이다. 위의 공식에 따르면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...이다. 만일, 단순하게 분할 정복 기법을 사용해서 10번째 피보나치 ..