CHAPTER 03 다이내믹 프로그래밍의 이해

3.1 다이내믹 프로그래밍이란?

다이내믹 프로그래밍 : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

메모이제이션과 다이내믹 프로그래밍 모두 개별 하위 문제를 단 한 번만 계산한다. 그러나 메모이제이션은 재귀 호출을 사용해 하향식으로 동작하는 반면, 다이내믹 프로그래밍은 상향식으로 문제를 해결한다.

다이내믹 프로그래밍의 주 적용 대상은 최적의 하위 구조 특성을 가지고 있으며 하위 문제를 반복해서 계산하는 복잡한 문제들입니다.

연습 : 부분 문자열 다루기

숫자열의 부분 문자열 중 앞부분 절반 숫자의 합과 뒷부분 절반 숫자의 합이 같은 문자열 가운데 가장 긴 부분 문자열의 길이를 구해보자.

문자열의 i번째 숫자부터 j번째 숫자까지의 합을 S(i, j)라고 한다.

1. 길이 1의 부분 문자열 숫자의 합 S(i, i)은 i번째 숫자의 값이다.
2. 길이 2의 부분 문자열 숫자의 합 S(i, j) = S(i, i) + S(j, j)이며, 이미 계산되어 있다.
3. 길이 3인 부분 문자열 숫자의 합 S(i, j)는 한 글자 문자열의 합과 두 글자 문자열의 합이고, 이미 계산되었다.

🌟 S(i, j) = S(i, k) + S(k + 1, j)

3.2 하향식 접근 방법과 상향식 접근 방법

다이내믹 프로그래밍은 재귀 호출 자체로부터 발생하는 부하를 피하기 위해 상향식으로 문제를 해결한다.

대부분의 경우 하향식으로 문제를 푸는 것보다 상향식으로 문제를 푸는 것이 좋다. 하지만 경우에 따라서는 하향식을 선택해야 할 수도 있다.