동적계획법(dynamic programming)

알고리즘 스터디

동적계획법(dynamic programming)

8.1 도입

프로그래밍 대회문제에서 가장 자주 출현하는 디자인 패러다임 중 하나

• 동적계획 법이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며, 우리가 전산학 전반에서 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍 (programming)이라는 단어와는 아무런 관련이 없음.
• dynamic programming의 적절한 번역은 동적 계획법임

중복되는 부분문제

• 동적 계획법 접근 방법 : 큰 의미에서 분할 정목과 같은 방식을 의미함.
• 분할정복과 동적계획법 차이 : 
  
  1. 문제를 나누는 방식.
  2. 계산 결과 재활용 - 동적계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용 -> 속도 향상
• 캐시 : 이미 계산한 값을 저장해 두는 메모리 저장소
• 중복되는 부분 문제(overlapping subproblems) 두 번 이상 계산되는 부분 문제
• 조합폭발(combinatorial explosion) 중복문제가 분할의 깊이가 깊어질수록 지수적으로 증가하는 것.
• 동적계획법의 목적 : 조합폭발 문제를 해결하기 위해 고안된 알고리즘 설계 기법

예 ) 가장 유명한 동적계획법 이항 계수

이항 계수 점화식

( n, r ) = ( n-1, r-1 ) + ( n-1, r )

코드 8.1 재귀 호출을 이용한 이항 계수의 계산

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

코드 8.1의 시간복잡도

• bino내에 반복문도 없음
• bino(n,r)의 수행시간은 재귀 호출이 몇번이나 이루어지는지를 계산하면 파악할 수 있음.
• 이때 주목할 점은 이항 계수의 특성상 같은 값을 두 번 이상 계산할 일이 빈번 하다는 점임

표, 이항 계수 (n, n/2)를 계산 할 때 필요한 함수 호출의 수

n	2	3	4	…	18	19	…	24	25
bino() 호출 횟수	3	5	11	…	97239	184755	…	5408311	10400599
bino2() 호출 횟수	3	5	8	…	99	109	…	168	181

메모이제이션 (memoization)

• 한번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법

코드 8.2 메모이제이션을 이용항 이상 계수의 계산

// -1로 초기화 해준다.
int cache[30][30];
int bino2(int n, int r){
    // 기저 사례
    if( r==0 || n == r ) return 1;
    // -1이 아니라면 한 번 계산했던 값이니 곧장 반환
    if( cache[n][r] != -1)
        return cache[n][r];
    return cache[n][r] = bino2(n-1, r-1) + bino2(n-1, r);
}

• 메모이제이션을 사용하면 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있기 떄문에 함수 호출 횟수가 엄청나게 감소라리라 예상할 수 있음. (위의 표 참고)

메모이제이션을 적용 할 수 있는 경우

• 참조적 투명성 (referential transparency) 
  함수의 반환 값이 그 입력 값만으로 결정되는지의 여부.
• 당연히 메모이제이션은 참조적 투명할수에 만 적용 할 수 있음.

코드 8.3 메모이제이션의 사용 예

// 전부 -1로 초기화해둔다.
int cache[2500][2500];
// a와 b는 각각 [0, 2500] 구간 안의 정수
int someObscureFunction(int a, int b){
    // 기저 사례를 처음에 처리한다.
    if(...) return ...;
    // (a,b)에 대한 답을 구한 적이 있으면 곧장 반환
    int& ret = cache[a][b];
    if(ret != -1) return ret;
    // 여기에서 답을 계산 한다.
    ...
    return ret;
}
int main(){
    // memset()을 이용해 cache 배열을 초기화 한다.
    memset(cache, -1, sizeof(cache));
}

메모이제이션의 시간 복잡도 분석

• 주먹구구 방식

  (존재하는 부분 문제의 수) * (한 부분 문제를 출 때 필요한 반복문의 수행 횟수)

• 물론 이 식은 수행시간 상한을 간단히 계산할 수 있는 방법일 뿐이며, 항상 정확하지는 않음.