[Dynamic Programming] DP 동적계획

동적 계획법 : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

두 가지 속성을 만족해야 DP로 문제를 해결할 수 있다.

1. Overlapping Subproblem

• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
• 문제를 작은 문제로 쪼갤 수 있다.

2. Optimal Substructure

• 문제의 정답을 작은 문제의 정답에서 구할 수 있다.

피보나치 수를 기준으로 보면

 

 

 

메모이제이션 : 실행된 결과를 저장해두었다가 재사용하는 최적화 기법

 

Top - Down :

• 큰 문제를 작은 문제로 나눈다. 
  fib(n) = fib(n-1) + fib(n-2)
• 작은 문제를 푼다.
  fib(n-1) 과 fib(n-2)를 호출해 문제를 푼다.
• 작은 문제를 풀었으니 큰 문제를 해결한다.
  fib(n-1) 과 fib(n-2) 결과를 바탕으로 fib(n)을 해결한다.

 

 

 

Tabulation : 테이블을 채워나가는 방식

 

Bottom -Up:

• 문제를 크기가 작은 문제부터 차례대로 푼다.
  fib(0) = 0, fib(1)  = 1
• 문제의 크기를 조금씩 키우면서 문제를 해결한다.
  fib(2) = fib(1) + fib(0)
  fib(3) = fib(2) + fib(1)
  ...
• 작은 문제를 모두 해결했기 때문에 큰 문제는 항상 풀 수 있다.
  fib(n)
• 필요하지 않은 하위문제도 해결할 때가 있다.
• 문제를 잘 분석해서 최적의 순서를 찾아야함
• CPU캐시에 친화적
• 재귀함수호출을 피할 수 있다.