dynamic programming

동적 계획법이라고 불리는 다이나믹 프로그래밍에 대해서 알아보자.

 

동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법으로, 부분 문제 반복과 최적 부분 구조를 가지고 있는 문제를 일반적인 방법에 비해 적은 시간안에 풀 때 사용한다.

 

기본 structure는 앞서 말한 것처럼 문제를 여러 하위 문제로 나눠 풀고, 그것을 결합해 최종적인 답을 도출해내는 것이다. 이 방법을 사용하면 계산횟수를 획기적으로 줄일 수 있어 하위 문제의 수가 많을 때 유용하다.

이 과정에서 메모이제이션(memoization)이라는 기술이 사용된다.

+메모이제이션: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장해 동일한 계산의 반복 수행을 제거해 프로그램 실행 속도를 빠르게 하는 기술로 동적 계획법의 핵심 기술임

 

보통 동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제의 최적화에 사용된다.