[알고리즘][개인공부] 동적 계획법 - HoonIOS

안녕하세요 HoonIOS입니다. :)

 

이번에는 어제 공부한 동적 계획법에 대해 알아보겠습니다.

 

동적 계획법이란?

- 동적 계획법은 큰 의미에서 분할정복과 같은 접근 방식을 의미합니다.

- 동적 계획법과 분할정복의 차이가 발생하는 부분은 문제를 나누는 방식입니다.

 

- 예를 들어 cde는 abcde를 해결할때와 cdefg를 해결할때 한 번씩 계산하고 그러면 c, d, e는 각각 세번씩 중복 실행이 됩니다.

 

- 이렇게 계산의 종복횟수는 분할의 깊이가 깊어질수록 더 증가하게 됩니다. 이런 문제를 해결하기 위해서 고안된 알고리즘은 동적계획법 입니다. 

 * 여기서 분할정복이란?
 - 주어진 경우를 작은 사례로 나뉘고 해답을 구할수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법입니다.
 - 대표적인 예시로 이진 정렬이 있습니다.

* 행렬을  n/2로 나눈후 최대한 작은 사례로 나누고 merge를 통해서 정렬을 하고 있는 이진정렬입니다.

- 동적 계획법 알고리즘의 가장 유명한 예중에 하나가 이항 계수의 계산입니다.

 

 * 이항계수란?

- 이항계수 ${n \choose r}$ 같이 표기하고 n개의 서로 다른 원소중에서 r개의 원소를 순서 없이 골라내는 방법의 수를 나타낸것입니다.  

- 이항 계수는 다음과 같은 점화식이 성립합니다.

- $ n \choose r $ = $ n - 1 \choose r - 1 $ + $ n - 1 \choose r $

- 이 점화식을 이용하면 n, r의 값이 주어질때 $(n \choose r)$ 의 값을 반환하는 함수 bino(n,r)코드를 작성해 보겠습니다.

int bino(int n, int r) {
//기저 사례: n = r, r = 0일때( 고를 원소가 없거나 n개랑 고를 r개가 같을때 )
if(r == 0 || n == r) return 1;
	return bino(n-1, r-1) + bino(n-1, r);
}

* 점화식이란
 - 재귀적으로 정의되는 수학적 함수를 의미합니다.

bino 트리, bino트리 중복제거

- 사진을 보면 bino(2,1), bino(1,0), bino(1,1)이 두번씩 중복호출이 되는것을 볼수 있습니다. 만약 중복을 제거하면 오른쪽 그림을 얻을수 있는데 여러번 계산하게 됨을 확인을 할수 있습니다.

- 이렇게 함수의 중복호출은 이항계수 n, r이 커짐에 따라 기하급수적으로 증가하게 됩니다.

- 함수의 중복 계산을 제거하기위해서 가장 좋은 방법은 캐쉬를 만드는것입니다.

따라서 중복 제거 계산을 하기위해서 n,r조합에 대해 답을 저장하는 캐시 배열을 만들어서 각 입력에 대한 반환값을 저장하겠습니다.

- 함수는 매번 호출할때마다 이 캐시 배열에 접근해 값이 저장되어 있는지 확인을 하고 저장이 되어 있으면 이것을 즉시 반환하고 만약 계산되어 있지 않은 값을 계산할때는 직접 계산하여 배열에 써놓고 반환을 합니다.

 

• 이렇게 함수의 결과값을 저장하는 장소를 마련해두고 한 번 계산한 값을 저장해 뒀다 활용하는 최적화 기법을 메모이제이션이라고 부릅니다.

* 메모이제이션을 이용한 이항계수 계산 예시

//캐쉬배열안에 모든 값을 -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);
}

 

- 이렇게 예시처럼 메모이제이션을 사용하면 모든 부분문제에 중복계산이 없다고 보장되어 있기 때문에 함수 호출 횟수가 엄청나게 감소한다고 예상을 할수가 있습니다.

- 두번이상 중복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법을 동적 계획법이라고 합니다.

- 메모지에이션은 참조적 투명 함수의 경우에만 적용을 할수 있습니다. 입력이 같은데도 외부 요소에 따라 다른값이 반환된다면 캐싱을 할수 없겠죠?

 * 참조적 투명함수?
- 함수의 반환값이 그 입력값만으로 결정된다는것을 말한다.
( 이말은 즉 입력에 매번 다른 결과값을 반환하면 안된다는 말입니다. )

메모이제이션 구현 패턴

- 동적계획법에서 가장 흔한 문제 유형중 하나인 만큼 한가지 패턴을 정해두고 항상 같은 형태로 구현을 작성하면 작성하기도, 버그를 찾기도 편해집니다.

 

- int someObescureFunction(int a, int b);라는 재귀함수가 있다고 하고 이 함수를 메모이제이션으로 바꿔 구현을 하는데 여기서 유의할점 4가지가 있습니다.

 

• 항상 기저사례를 제일먼저 처리합니다. 만약 제일 먼저 처리하지 않으면 범위를 벗어나 오류가 발생할수 있습니다.
• 함수의 반환값이 항상 0이상이라는 전제하에 cache[ ] 배열을 모두 -1로 초기화 했습니다. 만약 cache[ ]의 값이 -1이라면 이 값은 계산된적이 없는 경우 인것입니다.
  그렇지만 만약 이 함수가 반환값이 음수가 포함되어 있다면 이 방법은 써먹을수 없습니다...ㅠㅠ 왜냐하면 음수가 있다는것은 반환값이 -1로 나올수있는 확률이 있다는 뜻이기 때문이죠
• ret가 cache[a][b]에 대한 참조형입니다. 참조형 ret의 값을 바꾸고 cache[a][b]의 값도 변경하기 때문에 답을 저장할때도 매번 귀찮게 cache[a][b]라고 쓸 필요가 없습니다.
• memset( ) 함수를 이용하면 cache[ ]를 초기화 하는 부분입니다. for문보다 memset으로 배열을 초기화하는게 더 간편합니다.

- 이제 메모이제이션을 사용해서 int someObescureFunction(int a, int b);을 구현해보겠습니다.

//캐시 전부 -1로 초기화했다고 가정
int cache[2500][2500];
//반환값은 항상 int형 안에 들어가는 음이 아닌 정수
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, -1, sizeof(cache));
}

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

- 메모이제이션을 사용하는 알고리즘의 시간 복잡도 분석을 굉장히 간단하게 주먹구구로 계산을 할수 있습니다.

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

- bino2(n,r)은 부분 문제의 수는 최대 O($n^2$)이 되고 각 부분 문제 문제를 계산할때는 반복문이 없으므로 O(1)이 됩니다. 따라서 bino2(n,r)의 시간 복잡도는 $n^2$ 이 됩니다.

- 물론 주먹구구법칙으로 계산하는만큼 무조건 정확하지는 않습니다.

 

이렇게 동적계획법과 메모이제이션, 동적계획법과 분할정복의 차이를 공부해봤습니다 :)