[알고리즘 개념] 동적 계획법 (Dynamic Programming?)

동적계획법 (Dynamic Programming) ?

크기가 작은 부분 문제들의 해들을 결합하여 문제를 해결하는 방법을 말한다. 이전 단계들의 점화식을 세워 해결하기도 한다.

 

- 설계 원칙

1) 문제의 해를 구할 수 있는 재귀적인 성질을 설정한다.

2) 상향식 접근방식에 의해 크기가 작은 문제를 먼저 해결한 후, 크기가 큰 문제를 나중에 해결한다.

3) 크기가 큰 문제해결을 효율적으로 하기 위해, 크기가 작은 문제의 해는 테이블에 저장한다. (다시 계산 피하기 위해)

 

- 분할 정복 방식과의 차이점 : 분할 정복 방식에서는 서로 공유되는 같은 부분문제가 있다 하더라도 독립적으로 반복적인 계산을 하지만, 동적계획법에서는 이러한 반복을 피할 수 있으므로 효율적인 문제 해결이 가능하다.

 

대표적인 문제로 이항계수, 정수삼각형, 최장증가 부분수열, Floyd 알고리즘, 편집거리 등이 있다.

 

해당 알고리즘이 적용되는 프로그래머스 문제는 다음과 같다.