[알고리즘] 동적계획법, Dynamic Programming

  dynamic programming는 divide-and-conquer와 마찬가지로 재귀적인 속성을 가지고있지만, 더 나아가 최적화 문제를 다룬다는 특징 또한 가지고있다. 최적화 문제란 주어진 문제에 대하여 하나 이상의 많은 해답이 존재할 때 이 가운데에서 가장 최적인 해답을 찾아야 하는 문제를 일컫는다. 따라서 재귀적인 속성에 최적화 문제인 경우 dynamic programming으로 해결하면 된다. 

  dynamic programming은 bottom-up 방식을 이용하여 재귀적인 문제를 해결한다. 즉, 입력 사이즈가 제일 작은 문제부터 해결하여 점점 큰 문제를 해결해나가고, 이 때 나누어진 부분들 사이에는 서로 상관관계가 있다.

 

  dynamic programming 과 divide-and-conquer의 차이점을 정리하고 넘어가자.

 

<divide-and-conquer vs. dynamic programming>
-divide-and-conquer :  재귀적 속성 / 나뉘어진 부분들 간의 상관관계 x / top-down 방식 / 재귀호출 사용
-dynamic programming : 재귀적 속성+최적화문제 / 나뉘어진 부분들 간의 상관관계 o / bottom-up 방식 / 반복 사용

  서로 상관관계가 있는 문제의 예로 피보나치 수열이 있다.

 

피보나치 수열

 

  위 수열을 보면 이전 항들의 합이 다음 항의 결과가 됨을 알 수 있다. 이처럼 문제의 각 부분들이 서로 독립적이지 않고 다른 부분의 결과의 영향을 받는 경우 서로 상관관계가 있는 문제라고 한다. 서로 상관관계가 있음에도 불구하고 dynamic programming으로 해결하지 않고 devide-and-conquer로 해결하려 할 경우, 중복된 연산이 발생하여 비효율적이다. 

 

  dynamic programming의 알고리즘 설계전략은 다음과 같다.

 

<dynamic programming 알고리즘 설계전략>
1. 재귀 관계식 정립
2. 문제를 bottom-up방식으로 해결

  dynamic programming알고리즘으로 풀 수 있는 문제들로는 이항계수, Floyd's Algorithm, optimal binary search trees, TSP등이 있다. 이번 카테고리에서는 위 전략을 다양한 문제들에 적용하여 dynamic programming 알고리즘으로 문제를 해결해볼 예정이다.

 

 

 

[알고리즘] 이항계수, Binomial Coefficient | 설계 및 분석

 

[알고리즘] 플로이드 알고리즘, Floyd's Algorithms | 설계 및 분석 , 구현코드

 

[알고리즘] 최적 이진 검색 트리, Optimal Binary Search Trees | 설계 및 분석

 

[알고리즘] 외판원 문제, TSP(The Traveling Salesperson Problem) | 설계 및 분석