[알고리즘 문제해결전략] 8장 동적 계획법_1

동적 계획법 = dynamic programming 

 

[개념]

분할정복과 같이 처음 주어진 문제들을 더 작은 문제들로 나눈 뒤, 작은 조각들을 계산하고, 합쳐서 더 큰 문제에 대한 답을 계산해내는 접근 방식을 말합니다.

분할 정복과 다른 점은 '중복되는 부분 문제'를 메모리에 저장해서 한 번만 계산하게끔 만든다는 것입니다.

중복되는 부분 문제(overlapping subproblem) : 문제를 푸는데에 두 번 이상 계산 되는 부분문제 

 

왼쪽 : 중복되는 부분 문제 x(단순 분할 정복) / 오른쪽 : 중복되는 부분 문제o (동적 계획법)

위의 사진에서는 중복되는 부분 문제가 한 개 이지만, 깊이가 깊어질 경우 지수적으로 증가하게 된다. 

이러한 문제를 해결하기 위한 방법이 동적 계획법이다.

 

[예시 : 이항계수(조합)]

서로 다른 n개의 원소 중에 r개의 원소를 순서 없이 골라내는 방법의 수 

이 문제의 시간 복잡도는 어떻게 될까? => 재귀 호출이 몇 번이나 이루어지는지 계산

int bino(int n, int r) {
	if (r==0 || n==r) return 1;
    return bino(n-1,r-1) + bino(n-1,r);
   }

bino(4,2)를 계산한다고 할 때, bino(2,1)이 두 번 호출된다. 

n과 r의 숫자가 커짐에 따라 함수의 중복 호출 횟수는 기하급수적으로 증가하게 된다. 

여기서 n과 r이 정해져 있을 때, bino(n,r)의 값은 어떤 경우에든 항상 같다.

이 점을 이용해서 각 n,r조합에 대한 값들을 저장해놓으면, 같은 함수를 호출했을 때, 또다시 계산되지 않고 배열에 저장해놓은 값을 꺼내서 이용할 수 있다. 

(이전에 계산된 경우가 없는 함수는 새로 계산해서 배열에 저장해 놓아야 한다)

 

[Memorization]

함수의 결과를 저장하는 장소를 만들어두고, 계산한 값을 저장해 두었다가 재활용하는 최적화 기법 

memorization을 이용해 위의 bino함수를 수정해보자.

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);
}

memorization을 적용하면 속도의 향상을 꾀할 수 있다. 

 

[Memorization을 적용할 수 있는 경우]

프로그래밍에서의 함수는 함수의 입력 외에도 전역변수, 입력파일, 클래스의 멤버 변수 등에 따라 작동하기 때문에 입력이 같다고 항상 같은 값이 출력되지 않는다. 

int counter = 0;
int count(){
	return counter++;
}

count함수는 전역변수인 counter을 출력하기 때문에, 입력을 전혀 받지 않으면서도 매번 다른 결과를 반환한다. 

반면에 위에서 작성했던 bino(), bino2()는 입력이 같으면 항상 출력이 같은 함수이다.

 

참조적 투명성 (referential transparency) : 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부 

 

memorization은 참조적 투명함수에 경우에만 사용할 수 있다. 

count()처럼 입력이 같은데도 외부 요소에 따라 출력이 달라진다면, 미리 저장해둘 수 없기 때문이다.

 

[memorization 구현 패턴]

 

1. 항상 기저사례를 제일 먼저 처리한다.

2. 함수의 반환값의 범위를 고려하여 cache 값을 초기화한다

(memset()을 이용하면 다중 for문을 이용하는 것보다 편리하다. 하지만 0,-1과 같은 제한적인 경우에만 사용 가능)

3. ret은 cache[a][b]에 대한 참조형(reference)임을 기억하자.

(ret의 값을 바꾸면 cache[a][b]도 같이 바뀜)

int cache[2500][2500] //a와 b의 범위에 따라 크기 조절하기
int someFunction(int a, int b){
	if (...) return ... //기저사례 처리
    int& ret = cache[a][b];
    if (ret != -1) return ret; //이전에 구한 적이 있을 때
    
    ... //이전에 구한적이 없을 때, 새로 답 계산
    
    return ret;
}
int main() {
	memset(cache, -1, sizeof(cache)); //memory 초기화
    ...
}

 

[memorization 시간 복잡도 분석]

각 입력에 대해 함수를 처음 호출할 때와 그 다음으로 호출할 때 걸리는 시간이 달라진다.

따라서 복잡하지만, 주먹구구식으로 간단하게 계산해보자

 

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

 

bino2()의 경우를 생각해보자.

r의 최대치는 n이기 때문에 bino2()를 계산할 때 만날 수 있는 부분 문제의 수는 최대 O(n^2)이다 

각 부분문제 계산에 걸리는 시간은 반복문이 없기 때문에 O(1)이다.

따라서 bino2()의 시간 복잡도는 O(n^ 2)*O(n) = O(n^2)이다.

이 방법은 항상 정확하지는 않지만 간단히 계산해 볼 수 있는 방법이다. 

예를들어 모든 부분 문제 중에 일부분만 계산해도 답을 찾아낼 수 있는 문제라면 실제 수행시간이 식보다 훨씬 적을 것이다.