최근 수정:
Dynamic Programming. 줄여서 DP 라고 한다.
큰 문제를 작은 문제로 나누어 푸는 알고리즘 기법이다.
Dynamic Programming의 Dynamic은 아무 뜻이 없다...용어를 처음 사용한 사람[1]이 간지나서 썼다고 한다.
특정 문제를 DP로 풀려면 다음 두 가지 조건이 만족되어야 한다.
겹치는 부분 문제가 있어야 한다.
최적 부분 구조. 같은 문제는 구할 때마다 정답이 같다.
위의 두 가지 조건이 만족되었다면 구한 부분 문제의 정답을 어딘가에 메모해 놓는다. 이를 Memoization이라 한다. 코드의 구현에서는 배열에 저장하는 것이다.
탑 다운. 한국어로는 하향식이라고 한다.
구하고자 하는 문제를 작은 부분 문제로 나누고 작은 문제의 답을 구한 후 정답을 바탕으로 원래 문제를 푸는 방식.
흔히 재귀함수로 구현한다.
바텀 업. 한국어로는 상향식이라고 한다.
크기가 작은 부분 문제부터 차례로 풀어 나간다. 문제의 크기를 키우면서 답을 구한다. 보통은 마지막에 구한 답이 구하고자 하는 문제이다. [2]
흔히 반복문으로 구현한다.
처음 DP를 배울 때엔 어려울 수도 있으므로 문제를 많이 풀어보자. BOJ에 DP문제들이 많이 있다.
[1] Richard Bellman
[2] 항상 마지막이 답은 아니다. 구한 후 최대값을 찾는다거나 하는 연산이 필요할 수도 있다.