DP (Dynamic Programming)

• DP 이름의 기원 

     Dynamic Programming은 아무 의미가 없다.

     단지 이용어를 처음 사용한 Richard Bellman도 해당 이름이 멋있어 보여서 사용했다고 한다.  

   

     동적계획법이라고도 불린다. 

 

• DP의 정의 

     큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 의미. 

 

     큰 문제를 작은문제로 나눠서 푸는 알고리즘은 2개가 존재한다.  

     1) 동적계획법

     2) 분할정복

 

     이 두 알고리즘의 차이는 무엇일까? 

     차이점은 딱 1개가 있다. 

 

     바로 작은 문제가 중복해서 나오는지의 여부 이다.

     1) 동적계획법 

        작은 문제가 중복 되고, 중복되는 작은 문제의 답이 모두 동일하다. 

 

     2) 분할정복 

        작은 문제가 중복되지 않는다. 

        즉, 모든 작은 문제가 각각 1번씩 나온다.