Dynamic Programming

Dynamic Programming

다이나믹 프로그래밍은 특정 알고리즘이 아닌 디자인 패러다임입니다. 우리가 알고 있는 이러한 디자인 패러다임은 분할 정복, 백트레킹 등이 있습니다.

• 최적화 문제: optimal value를 찾는 솔루션, 최대화 최소화 문제
  • 우리는 최적의 선택을 모른다.
  • 따라서 우리는 미리 계산한 하위 문제의 비용을 기반으로 하위 문제를 모두 시도한다.
• 우리가 내리는 선택에 따라 해결해야 할 하위 문제가 결정된다.

 

최적화 예시

• 최단거리 문제: 포항에서 서울까지가는 길은 많습니다. 최단 경로, 가장 경치 좋은 경로, 가장 빠른 경로를 계산하려고합니다.
• 잡 스케줄링: 여러 프로세서에서 작업 세트를 예약하는 방법에는 여러 가지가 있습니다. 프로세서의 다양한 기능과 작업의 다양한 리소스 요구 사항을 감안할 때 가능한 한 적은 시간에 가능한 한 많은 작업을 완료 할 수 있도록해야합니다.

 

 

동적 계획법 설계

• A dynamic programming은 동일한 유형의 더 작은 (또는 더 단순한) 문제 $ S_1, \ S_2, \ ..., \ S_m $ 의 솔루션에서 동적으로 구축하여 주어진 문제에 대한 솔루션 S를 구성하는 설계 전략입니다.
• S = $ combine(S_1, \ S_2, \ ..., \ S_m) $

 

• 주어진 작은 문제 $ S_i $에 대한 해결책은 그 자체로 더 작은 하위 문제에 대한 해결책 등으로 구성됩니다.
• 우리는 가장 작은 문제 인스턴스에 대한 알려진 솔루션으로 시작하여 상향식 방식으로 구축합니다.

 

 

동적 계획법 vs 분할 정복

Fibonacci Number Example

 

Divide and Conquer

Fib (n){ 
  if (n < 2) return n; 
  else return Fib(n-1) + Fib(n-2); 
}

 

Dynamic Programming

Fib (n){
  int fib[n+1];
  
  fib[0] = 0; 
  fib[1] = 1;
  
  for (int i=2; i < n; i++)
    fib[i] = fib[i-1] + fib[i-2];
  
  return fib[n];
}

분할 및 정복 알고리즘은 일반적인 하위 문제를 반복적으로 해결하면서 필요한 것보다 더 많은 작업을 수행 할 수 있습니다. 동적 프로그래밍 알고리즘은 모든 하위 문제를 한 번만 해결 한 다음 그 답을 표에 저장하므로 하위 문제가 발생할 때마다 답을 다시 계산하는 작업을 피할 수 있습니다. 동적 프로그래밍은 일반적으로 최적화 문제에 적용됩니다.