[Algorithm] Dynamic Programming vs Memoization

Dynamic Programming VS Memoization

공통점

- 배열을 저장공간으로 사용한다.
- 미리 계산한 값을 재사용 함으로써 반복 계산을 방지한다.

Dynamic Programming

하나의 문제를 작은 하부 문제로 나누어 해결하는 방법.

작은 문제부터 해결하며 현재 계산하고 있는 문제는 "이전에 계산된 문제의 답"을 이용하여 풀 수 있어야 한다.

작은 문제부터 해결해 나간다고 하여 "Bottom-UP"방식이라고 한다.

재귀호출을 사용하지 않기 때문에 오버헤드가 작다.

Memoization

큰 문제를 해결하기 위해 작은 문제를 호출하여 해결하는 방법.

단 문제를 해결하여 나온 답은 캐싱하여 재사용함으로써 반복 계산을 방지한다.

최종 문제인 가장 큰 문제부터 호출한다고 하여 "Top-Down"방식이라고 한다.

일반 재귀호출보다 속도가 훨씬 빠르지만, 재귀호출로 인한 오버헤드가 발생한다.

---

이항계수 문제로 보는 차이점 - n개의 수 중 k개를 선택할 때 나올 수 있는 전체 경우의 수

Dynamic Programming

intbinomialByDP(n,k){
   //n개중에 k개
   int[][] DP=newint[n+1][n+1];/
   for(inti=1;i<=n; i++){//전체 수
       for(intj=0; j<=i&&j<=k; j++){//선택해야하는 수
           if(i==j||j==0) {
               DP[i][j]=1;
               continue;
          }
           DP[i][j]=DP[i-1][j] +DP[i-1][j-1];
           //j를 뽑아서 i-1개 중 j-1개를 뽑아야 하거나, j를 뽑지 않아서 i-1중 j개를 뽑아야하거나
      }
  }
   returnDB[n][k];
}

Memoization

int[][] mem=newint[][]; // -1로 초기화
intbinomialByMem(n,k){
   if(n==k||k==0)
       return1;
   if(mem[n][k]!=-1)
       returnmem[n][k];
   mem[n][k]=binomialByMem(n-1,k-1)+bunomialByMem(n-1,k);
   returnmem[n][k];
}