서랑의 개발 블로그

✅ 동적계획법(Dynamic Programming) 동적계획법(Dynamic Programin)이란 큰 문제를 작은 문제로 나누어 해결 한 뒤 그 해를 활용하여 큰 문제를 해결해 나가서 결국 최종 문제를 해결하는 알고리즘이다. Memoization(메모이제이션)기법 : 해결한 문제의 해를 저장해 둔 뒤, 똑같은 문제가 발생하였을 때 저장해 놓은 해를 사용함으로써 중복 연산을 하지 않고 빠르게 해결하는 기법이다. ✔ 동적 계획법 예시 피보나치수열 점화식 f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) 피보나치수열의 점화식을 그림으로 표현해보면 위 그림과 같다. 위 그림을 보면 동일하게 중복돼서 사용되는 함수가 있다. f(0), f(1), f(2)가 반복되어서 사용되고 아마 숫자가 ..