동적 계획법(Dynamic Programming)_1.개념

1. 동적 계획법(Dynamic Programming)이란?

분할 정복과 같은 접근방식을 갖고 있습니다. 
처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고,
이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문입니다. 

차이가 발생하는 부분은 문제를 나누는 방식입니다.
부분문제가 여러번 사용될 수 있을 때 여러번 중복 계산하는 것이 아닌, 
한번만 계산하고 저장해둬 재활용해 사용합니다.

(a)서로 연관이 없는 부분문제	(b)서로 의존하고 있는 부분문제

(a)는 서로 연관이 없어 단순히 재귀 호출을 통해 문제를 풀어도 한 부분문제를 한 번만 해결합니다.
(b)는 부분문제가 서로 의존하고 있어, 단순 재귀로 풀면 중복 계산이 많아집니다.
 예를 들면 cde는 abcde를 해결할 때, cdefg를 해결할 때 한번씩 계산해야 하고,
 그러면 cde가 의존하는 c, de는 각각 세번씩 계산됩니다.

계산의 중복횟수는 분할의 깊이가 깊어질 수록 지수적으로 증가합니다.

이를 해결하기 위해 고안된 알고리즘 설계기법이 동적 계획법입니다.

2. 동적계획법 예시 - 이항계수의 계산

 이항계수는 n개의 서로 다른 원소 중 r개의 원소를 순서없이 골라내는 방법의 수를 나타낸 것으로,
아래 점화식이 성립합니다.

  

위 점화식을 코드로 짜면,

int bino(int n, int r)
{
    //기저 사례: n=r(모든 원소를 다 고르는 경우) r=0(고를 원소가 없는 경우)
    if(r==0 || n==r) return 1;
    return bino(n-1, r-1) + bino(n-1, r);
}

이항 계수는 특성상 재귀 호출을 하게 되면 같은 값을 두 번 이상 계산할 일이 빈번합니다.

(a) bino(4,2) 중복 제거 전	(b) bino(4,2) 중복 제거 후

(a)에서 bino(2,1)는 bino(3,1)과 bino(3,2)에서 모두 호출됩니다.
bino(2,1)은 bino(1,0), bino(1,1)을 재귀 호출하여 이 경우도 두번씩 호출됩니다.
중복을 없애면 (b)를 얻을 수 있는데, 계산의 수가 줄어듬을 알 수 있습니다.

중복된 계산을 막기 위해 저장된 결과를 배열에 저장한 뒤,
다음에 계산이 필요할 때는 저장된 값을 불러옵니다.
이러한 기법을 메모이제이션(memoization)이라고 부릅니다.

int cache[30][30];
int bino2(int n, int r)
{
    if(r==0 || n==r)      return 1;
    if(cache[n][r] != -1) return cache[n][r];
    
    return cache[n][r] = bino2(n-1, r-1) + bino2(n-1, r);
}