[Definition] DP(Dynamic Programing) 동적계획법

티스토리 뷰

카테고리 없음

Zartt 2021. 4. 2. 16:39

동적 계획법이라고 불려지고 있지만, 사실 이 기법은 단어의 의미와 크게 상관없다고 합니다(출처: DP 만든이)

주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과로 주어진 문제를 푼다.

분할정복과 유사해 보이는 정의입니다. 하지만 분할정복은 나누어진 문제가 중복되지 않고, DP는 중복되는 문제가 발생합니다.

점화식에 관련된 문제를 풀다보면 재귀 함수를 이용해 풀이하는 경우가 존재합니다.

재귀 함수를 사용하면 보기에도 직관적이고 구현하기 쉽습니다. 하지만 점화식의 N값이 커지면 계산양이 기하급수적으로 증가할 수 있다는 단점이 있습니다.

이 점을 보완한 방법이 ‘DP’ 라고 할 수 있습니다.

재귀 함수의 경우 이미 계산 했던 값을 다시 또 계산해야하지만, DP에서는 이전의 계산을 기억했다가 다음번에 계산할 때 기억했던 값을 불러와 사용합니다. 이것을 ‘메모이제이션’ 이라고도 합니다.

DP의 대표적인 구현 방식으로는, 메모이제이션을 기반으로한 재귀 함수기법과 반복문이 있습니다.

재귀함수는 탑 다운 방식으로 이루어지고, 반복문은 바텀 업 방식으로 구현됩니다.