티스토리 뷰
'동적 프로그래밍'에서 '프로그래밍'이란 컴퓨터 프로그래밍을 뜻하는 말이 아니라 테이블을 채워나가면서 값을 구하는 방법을 일컫는다.
'dynamic programming'을 동적 계획법으로 번역하기도 한다.
메모이제이션은 위에서 아래로 문제를 풀고, 동적 프로그래밍은 아래에서 위로 풀어 간다는 점, 메모이제이션에서는 함수를 호출하는 비용이 드는 반면 동적 프로그래밍은 함수 호출이 없다는 점에서 두 가지 방법은 약간의 차이가 있다. 하지만 부분문제들의 해를 배열에 저장하는 아이디어는 본질적으로 같다.
동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
우리는 동적 계획법을 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법이라고 생각할 수 있다. 그러나 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법이라고 말할 수 있다.