피보나치 수 (2) 썸네일형 리스트형 [알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming) 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조(Optimal Substructure)라고 한다. 이 최적 부분 구조가 지켜진 상태에서 문제에 대한 해답을 찾는 과정이 바로 동적 계획법이다. 동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 예시로 피보나치 수를 보자. 피보나치 수는 다음과 같다. 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 이를 점화식으로 나타내면 다음과 같다. $$\begin{align} f(1) & = f(2) = 1 \\ f(n) & = f(n-1) + f(n-2) \end{align}$$ \(n\)의 피보나치 수는 더 작은 크기인 \(n-1\)의 피보나치 수와.. [프로그래머스/C++] 피보나치 수 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.. 이전 1 다음