동적계획 알고리즘(Dynamic Programming)

• 입력 크기가 작은 부분 문제들을 우선적으로 해결
• 이전에 해결한 해를 이용해 큰 크기의 부분 문제들을 해결
• 최종적으로 원래 주어진 입력의 문제를 해결가능

동적계획 vs 분할정복

• 동적 계획 알고리즘은 문제가 분할되는 구간이 없음

• 동적 계획 알고리즘은 부분 문제들 사이에 의존적 관계가 존재함

  • 이러한 관계가 문제 또는 입력에 따라 다르고, 대부분 뚜렷이 보이지 않아 함축적 순서라고 부름

• 분할 정복 알고리즘은 부분 문제의 해를 중복해 사용하지 않음

1. 부분 문제의 해 구하기

1.1. 상향식(Bottom-up) 방법

• 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 더 큰문제의 정답을 풀어나감
• 작은 문제의 정답을 테이블에 기록하고, 해당 테이블을 점차적으로 확장해다가는 의미에서 Tabulation이라 부름

1.2. 하향식(Top-down) 방법

• 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 풀어나감
• 이미 푼 문제와 답을 메모하여 참조한다는 의미에서 Memoization이라고도 부름

2. 문제 설계하기

1. 문제가 분할되는 것을 확인
2. 연산을 분석하여 부분문제가 여러번 나타나는지 확인
3. 여러번 연산한다면 DP
4. 점화식을 유도