동적 프로그래밍(DP)의 2가지 조건

• [ ] DP를 적용하기 이전에 체크해봐야 할 2가지 조건이 있다 !

최적 부분 구조

: 큰 문제의 최적해는 부분(sub) 문제의 최적해로 구할 수 있어야 한다.

기억하며 풀기(Memoization)

: 동일한 문제를 반복해서 구해야 하는 경우, 한 번 계산된 결과는 저장해 두었다가 활용하는 방식으로 중복 계산을 막는다. → 대표적인 예로 피보나치 수열이 있다.

[Algorithm] 분할정복(Divide-Conquer) & 그리디(Greedy) & 동적계획법(DP)

알고리즘 문제: 멀리 뛰기

• [ ] 이 문제는 이전에 풀었던 문제처럼 단순하게 n번째 피보나치 수를 구하는 문제가 아니라, 피보나치 수를 구하는 점화식을 활용하는 문제였다.

피보나치 수열의 점화식과 문제의 관계

• [ ] 이 문제에서의 논리가 피보나치 점화식과 동일한 구조를 가지고 있음을 알 수 있다 !

n칸까지 가는 방법을 계산할 때, n-1칸에서 1칸을 뛰거나, n-2칸에서 2칸을 뛰는 두 가지 방법을 생각할 수 있다. → n칸까지 도달할 수 있는 방법의 수 = n-1칸까지 도달하는 방법 + n-2칸까지 도달하는 방법

실패 코드