3. Dynamic Programming - 경우의 수와 확률
다이나믹 프로그래밍은 경우의 수를 세거나 확률을 계산하는 문제에도 많이 사용된다.
경우의 수를 계산하는 문제는 많은 경우 재귀적인 특징을 가지고 있기 때문이다.
그런데 경우의 수를 계산하는 경우 경우의 수가 굉장히 커져 32비트 정수형에 담기지 못할 수도있다.
따라서 오버플로에 주의 하여야 한다.
예제 - 타일링 방법의 수 세기 문제
문제를 해결하기 위해 완전 탐색을 이용해 모든 답을 만들면서 방법의 수를 세어볼 수가 있다.
그 다음 메모이제이션을 적용하여 다이나믹 프로그래밍 알고리즘으로 바꾸도록 한다.
완전 탐색 알고리즘은 재귀 함수를 통하여 구현하는데, 그러기 위해서 전체 문제를 부분 문제로 나누어 보자.
한번의 재귀 호출에서, 즉 하나의 부분문제에서 주어진 사각형의 가장 왼쪽 세로줄을 채운다고 생각한다.
그러면 위와 같이 두가지 방법으로 왼쪽 세로줄을 채울 수 있게 된다.
이 두가지 외의 다른 방법은 존재하지 않으며, 이 두가지 방법을 모두 포함하는 방법 또한 존재하지 않는다.
따라서 경우의 수를 셀 경우 왼쪽 방법 또는 오른쪽 방법 중 하나를 선택하고 남은 사각형에 대해서 재귀적으로 해결하면
경우의 수를 중복해서 세거나 빼놓고 세는 경우는 없을 것이다.
왼쪽 방법은 남은 사각형이 2*(n-1) 의 크기가 되고, 오른쪽 방법은 남은 사각형이 2*(n-2) 의 크기가 된다.
재귀함수 tiling(n) 의 정의를 2*n 크기의 사각형을 타일로 채우는 방법의 수 반환이라고 한다면,
재귀함수를 다음과 같이 구현할 수 있다.
tiling(n) = tiling(n-1) + tiling(n-2)
위의 재귀함수 점화식에 메모이제이션을 적용하여 다이나믹 프로그래밍 알고리즘을 구현할 수 있다.
// 타일링의 수를 세는 다이나믹 프로그래밍 알고리즘
const int MOD = 1000000007;
int cache[101];
int tiling(int n) {
// base case : n이 1이면 2*1 사각형만 남은 것이기 때문에 방법의 수는 1
if (n <=1) return 1;
// 메모이제이션 적용
int& ret = cache[n];
if( ret != -1) return ret;
return ret = (tiling(n-1) + tiling(n-2)) % MOD; // MOD 값으로 나눈 나머지를 반환한다.
}
예제 - 삼각형 위의 최대 경로 개수 세기 문제
이 문제는 이전에 메모이제이션 문제로 삼각형 위의 최대 경로의 크기를 구하는 문제와 연결된다.
삼각형의 최대 경로의 크기를 구하는 함수를 이용하여 각 위치에서 마지막 줄까지의 경로 중 최대 크기를 각 위치에 저장하고,
각 위치에서 바로 아래칸과 오른쪽 아래칸의 경로 크기를 비교하여 어느 쪽으로 갈지 선택한다음
그 위치에 대하여 재귀적으로 가능한 경로의 개수를 세도록 한다.
위와 같이 바로 아래칸과 오른쪽 아래칸의 경로의 크기를 비교해서 더 값이 큰 쪽으로 내려가도록 한다.
두 칸의 경로의 크기가 같으면 두 칸 모두 갈 수 있기 때문에(어느쪽으로 가도 최대경로를 만들 수 있기 때문에) 두개의 경우를 모두 세도록한다.
count(x,y) = (x,y) 에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수
위와 같이 재귀함수를 구성하면, 다음과 같이 점화식을 만들 수 있다.
// 삼각형 위의 최대 경로의 수를 찾는 다이나믹 프로그래밍 알고리즘
int cache[100][100];
int count(int x, int y) {
// base case : 마지막 줄이면 경우의 수 1 리턴
if( x == n-1) return 1;
// 메모이제이션
int& ret = cache[x][y];
if( ret != -1) return ret;
ret = 0;
if(path(x + 1, y) <= path(x + 1, y + 1)) ret += count(x + 1, y + 1);
if(path(x + 1, y) >= path(x + 1, y + 1)) ret += count(x + 1, y);
return ret;
}
예제 - 달팽이 문제
우선, 비가 올 확률을 50%라고 가정하고 문제를 풀어보자.
그러면 달팽이가 하루동안 1미터를 올라갈 확률과 2미터를 올라갈 확률이 같아진다.
m일 안에 달팽이가 우물을 탈출 할 수 있을 확률은 전체 경우의 수 2^m 개에서 달팽이가 우물을 탈출한 경우의 수를 계산하면 된다.
해당 문제를 m개의 부분 문제로 쪼갠다고 하면, 각 부분 문제는 하루동안 1미터 또는 2미터를 올라가고 나머지 깊이에 대해서 재귀호출로 문제를 해결할 수 있다.
그러면 재귀함수는 현재까지 올라온 높이와 몇일이 지났는지를 입력받으면 앞으로 달팽이가 우물을 탈출할 경우의 수를 반환하면 된다.
// 달팽이 문제를 해결하는 다이나믹 프로그래밍 알고리즘
int n,m;
int cache[1000][2000]; // 열의 경우 매일 2미터씩 올라간다고하면 최대 2000미터까지 올라갈수 있기 때문에 최대크기 2000
int climb(int days, int climbed){
// base case : m일이 모두 지났을 때 climbed가 n 이상일때 (우물을 탈출했으면) 1리턴
if( days == m){
if(climbed >= n) return 1;
else return 0;
}
// 메모이제이션 적용
int& ret = cache[days][climbed];
if(ret != -1) return ret;
// 오늘 하루동안 1미터 올라가거나 2미터 올라감
return ret = climb(days+1, climbed+1) + climb(days+1, climbed+2);
}
위의 코드에서 비가올 확률을 50% 라고 가정했기 때문에, climb(days+1,climbed+1) 의 확률과 climb(days+1,climbed+2) 의 확률이 동일하다.
그러나 원래 문제대로 비가 올 확률이 75% 라고 하면 1미터 올라갈 확률이 75%가 되므로
점화식을 다음과 같이 바꿔야한다.
climb(day,climbed) = 0.75 * climb(days+1, climbed+1) + 0.25 * climb(days+1, climbed+2)
경우의 수 계산하기 레시피
1. 모든 답을 직접 만들어서 세보는 완전 탐색 알고리즘을 설계한다.
이 때 경우의 수를 제대로 세기 위해서는 재귀 호출의 각 단계에서 고르는 각 선택지에 다음과 같은 속성이 성립해야한다.
- 모든 경우는 이 선택지들에 포함된다.
- 어떤 경우도 두 개 이상의 선택지에 포함되지 않는다.
2. 최적화 문제를 해결할 때처럼 이전 단계들에서 결정한 요소들에 대한 입력을 없애거나 최소화한다.
재귀함수는 앞으로 남아있는 조각들을 고르는 경우의 수만을 반환해야 한다.
3. 메모이제이션을 적용한다.