동적 계획법 Dynamic programming

동적 계획법

복작한 문제를 작은 하위 문제로 나눠 해결하고, 그 결과를 조합하여 최종 해답을 얻는 알고리즘
설계 기법을 말한다.
작은 부분 문제들의 해를 미리 구해서 중복 계산을 방지한다

필수 조건

최적 부분 구조

• 큰 문제의 최적 해가 작은 문제의 최적 해를 포함

중복 부분 문제

• 같은 부분 문제가 여러 번 반복되어야 함

접근 방법

하향식 접근

• 계산한 결과를 메모리에 저장하고 재사용
• 재귀식 접근
• 상대적으로 입력이 적은 경우에 사용

상향식 접근

• 하위 문제의 결과를 표에 저장
• 입력이 많은 경우에 적합
• 하위 문제가 한번에 구해지지 않는 경우에 사용

다시 한번 생각 해보자!

1. 문제의 요구사항을 점화식의 결과가 되도록 유도한다
2. 문제를 작은 부분문제로 쪼갠다
3. 동적 배열의 차원 수를 줄일 수 있는지 한번 더 검토한다