dynamic programming

[알고리즘] 동적 계획법 Dynamic Programming

동적 계획법 (DP) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 해결하고 그 결과를 저장하여 다시 큰 문제를 해결하는 알고리즘, 문제 해결 패러다임 상향식 접근법, 최하위 해답을 구하고 이를 이용하여 상위 문제를 풀어감 Memorization 기법 사용 프로그램 실행 시 이전 계산 값(작은 문제)을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술임 큰 문제를 작은 문제로 쪼개서 답을 저장하고 재활용 하기에 '기억하며 풀기' 라고도 불림 ex) 피보나치 수열 재귀함수와 다른 점은 $(F_{2}$ 가 여러번 사용되는데 동적 계획법은 저장하여 다시 계산하지 않고 재귀함수는 하나하나 다 계산하여 시간이 오래 걸린다 $O(n^{2}) \to O(f(n))$ 분할 정복 큰 ..