이번에는 DP에 대해 정리하고, 문제를 기준으로 이해해보자!
위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.
10
10 -4 3 1 5 6 -35 12 21 -1
동적계획법, 알고리즘을 풀 때 흔히 언급되는 DP는 큰 문제를 작은 문제들로 나누어 푸는 방법이다.
각 하위 문제들을 해결하고 저장하여 같은 하위 문제가 나왔을 때 이를 이용한다.
쉽게 말해서 문제를 작게 나누고 해결한 값을 저장해서 활용한다는 것이다.
위 예제를 통해 먼저 살펴보자.
위 예제는 최대 부분 수열의 합을 구하는 문제로 연속된 숫자의 합이 가장 클 때를 선택해야 한다.
dp 배열을 사용하여 숫자의 합을 구해나갈 때, 현재의 최적 값이 이전의 최적 값으로 부터 구해낼 수 있기 때문이다.
연속된 값을 찾기 위해 처음부터 더하면서 비교하다 보면 아래와 같은 식을 얻을 수 있다.
dp[n] = Math.max(dp[n-1] + array[n], array[n]);
이를 점화식이라고 부르며, DP 문제에서는 이를 찾는 것이 가장 큰 핵심이다.