꾸준히 개발하기

동적 계획법(DP)은 어렵거나 큰 문제를 간단하고 작은 여러개의 문제로 나누어 풀고 작은 문제의 답들을 이용하여 원래 문제의 답을 구하는 방식이다.

다음의 특징을 갖고 있다,

1. 최적 부분 구조
: 문제의 정답이 작은 문제에 대해서도 정답이어야 한다. 

2. 부분 문제 반복
: 문제를 여러 개의 작은 문제로 나눌 수 있으며, 나눈 작은 문제들을 전체 문제를 푸는 방법과 같은 방법으로 풀 수 있어야 한다.

DP 문제는 하향식, 상향식 두 가지 방법으로 접근할 수 있다.

하향식 방법의 경우 큰 문제를 풀 수 있는 작은 문제가 될 때까지 나눈 후, 작은 문제들을 풀어 얻은 정답들을 합쳐가며 큰 문제의 답을 구하는 방식으로, 주로 재귀 함수를 이용하여 구현한다.

상향식 방법은 가장 작은 문제부터 시작하여 큰 문제를 풀 수 있을 때까지 차례대로 문제들을 풀어나가는 방식으로 주로 반복문을 이용해 구현한다.