3. Dynamic Programming

3.1 Dynamic Programming

한국어로는 동적계획법이라고 하며 쉽게 풀어서 말하면 일단 제일 기본적으로 구해야 할 것을 구하고 그 구한 값을 다음값을 구하는데 쓰는 방법이다. 저번의 Divive and Conquer은 큰 그림을 보고 나서 차근차근 내려왔지만 동적계획법은 Bottom up으로 아래서부터 차근차근 구하면서 올라간다.

The Binomial Coefficient

예를 들어 우리가 잘 아는 C(수학)을 예로 들어보자

• Divide and Conquer

Divide and Conquer 방식으로 하면 저번에 피보나치 수열처럼 recursive가 되면서 구했던 것을 또 구하게 되고 매우 비효율 적이게 된다.

계산값은 옳게 나온다. 하지만 아까도 말했듯이 매우 비효율 적이다.

-Dynamic Programming

Bottom-up 으로 해서 밑에 숫자를 구하고 저장해두고 다음 숫자를 구하는데 쓰고 이렇게 구해보자

계산식이 매우 간단해지면서 좋은 방법인 것을 알게 되었다. 

하지만 항상 Dynamic Programming이 좋은 것은 아니다. Divide and Conquer이 좋은 algorith도 매우 많다.

3.2 Graph Theory

• Floyd's Algortithm for shortest paths problem

여러가지 방법 중에 optimization(최상)의 조건을 가진 답을 구하는 문제이다.

• Brute-force Algortithm for shortest paths

모든 가는 방법을 구하고 그 중에 length가 가장 짧은 것을 찾는 방식이다.

• Dynamic Programming Strategy for shortest paths

지금 부터는 용어가 중요하다. W와 D를 꼭 이해해야 넘어갈 수 있다.

• W : i에서 j까지 가는 길의 Length이다. 0이면 i = j 무한대면 가는 길이 없다는 것이다. 
• D : 점 {1,2,...,k}만을 경유 가능한 점들로 고려하여 i에서 j까지의 모든 경로중 가장 짧은 것을 의미한다. 1에서      k까지의 어떤 점이든 지나도 된다.

D에대해 좀더 알아보자 k != i , k != j, k = 0이면 i에서 j까지 가는데 어떤 점도 경유하지 않는 것이기 때문에 i에서 j까지 거리를 나타낸다

k가 1이면 점 1을 경유하여 가는 경로중 가장 짧은 거리이다. 이걸 일반화 하면 밑에있느 식이 나온다.

Designing an algorithm for shortest path

W 표를 보고 D를 구할 수 있어야한다.!

• Floyd's Algorithm