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

  Dynamic Programming은 대회나 시험용으로 가장 많이 나오는 유형이다. 이 방법을 이해하면 문제를 60line 이내로 해결가능하나 이해를 하지 못하면 해결이 거의 불가능하다. 

 

1. Dynamic Programming이란?

  큰 문제를 해결하기 위해서 큰 문제를 작은 문제로 나누고 작은 문제들의 답을 통해 큰 문제의 답을 구하는 것이다.

 

2. 적용법

  Dynamic Programming의 3대 요소는 데이터 저장용 Table, Dynamic Program 식, 기저조건(n=0, n=1)이 있다. 동적계획법은 거꾸로 프로그래밍하는 것이다. 이 말이 무엇이냐 하면 부산에서 서울까지 가장 빠른 시간 내에 가고자하면 부산부터 출발하는 것이 아니라 서울 근처 강릉, 파주와 같은 도시로 가는 가장 짧은 길을 알고 있다고 가정하고 거기서 서울까지 가는 시간과 이전 시간을 더해 더 빨리 서울에 도착할 수 있는 길을 택하는 것이다.