[Algorithm] 동적 프로그래밍

동적 프로그래밍

큰 문제의 해답에 작은 문제의 해답이 포함되어 있는데,

이를 재귀 호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에

이 재귀적 중복을 해결하는 방법

 

2가지 성질

1. 최적 부분구조

큰 문제의 해답에 그보다 작은 문제의 해답이 포함된다.

 

2. 중복 호출로 인한 심각한 비효율의 발생

한 번만 구해서 저장해 놓았다가 사용해도 되는 값들을 계산할 때마다 호출하는 비효율

 

 

거의 모든 재귀적 알고리즘은 최적 부분구조를 구현한다. 병합정렬, 퀵정렬 등도 최적 부분구조를 갖는다.

하지만, 이들은 재귀적 구현에서 중복이 발생하지 않는다. 이 점에서 동적 프로그래밍의 대상이 되는 문제와 다르다.

 

 

동적 프로그래밍을 구현할 때, 중복적으로 호출되는 값을 따로 저장해두고 그 값을 호출한다.