[Algorithms] Dynamic Programming

재밌는것 같은데 너무 어려운 다이나믹 프로그래밍.ㅡㅜ

Dynamic Programming(동적 프로그래밍)은 
문제를 작은 인스턴스들로 나누고 Bottom-up order로 풀어나가면서 문제의 값을 저장해놓고
필요할때 가져와 쓰는 방식으로 문제를 해결하는 방식을 의미한다.

Divide and conquer와의 공통점은 문제를 작은 단위로 나누어 해결한다는 것이고
차이점은 Divide and conquer는 Top-down 방식으로 위에서부터 진행하는 방식인데
Dynamic Programming은 Bottom-up 방식으로 작은 인스턴스부터 풀어나가면서 그 값을 더 큰 인스턴스를 풀 때 이용한다.
기존에 진행된 smaller instance의 값들은 주로 이차원 array에 저장되며 영향을 받는 변수의 수에 따라 배열의 차원은 더 늘어날 수도 있다.

재귀 피보나치를 반복으로 구현,
C(n,k) = C(n-1, k-1) + C(n-1, k) 성질을 이용한 Binomial coefficient 계산,
그래프간 모든 버텍스간의 최단경로를 계산하는 Floyd 알고리즘,
검색할 확률이 높은 것을 root에 가깝도록 형성하는 Optimal BST 알고리즘,
시작 vertex부터 다른 모든 vertex를 방문하고 자신의 버텍스로 다시 돌아오는 시간을 계산하는 Traveling Saleesperson problem 등등의 문제를 해결하는데 이 기법을 사용할 수 있다.

재귀를 반복으로 바꾼다는 점에서도 알 수 있겠지만 Complexity가 비약적으로 감소한다.
예를 들어 Floyd 알고리즘같은 경우에도 simple하게 접근하면 빅 오메가 n!의 복잡도를 가지지만
다이나믹 프로그래밍을 이용할 경우 n의 3제곱의 오더를 가진다.
그만큼 효과적이지만 이해하기 어려운 측면들도 있는 것 같다.ㅜ

많이 보는 것만이 답인듯.
Practice makes perfect.