6-3. 다이나믹 프로그래밍 - 경우의 수와 확률

ParkJunHa·2023년 7월 6일

Algorithm

목록 보기

10/15

개요

동적 계획법은 애초에 최적화 문제를 풀기위해 고안되었지만, 경우의 수나 확률을 계산하는데에도 흔히 사용한다.
대개 경우의 수를 사용하는 문제에서 답은 지수적으로 증가한다. 그래서 많은 경우에서의 답이 일반적으로 우리가 사용하는 컴퓨터에서 표현할 수 있는 정수의 범위를 넘어가게 된다. 따라서 이러한 문제들은 답을 어떤수 $M$ 으로 나눈 나머지를 출력하라고 요구한다.

예시

BOJ-1793 타일링 문제는 $2\times n$ 사각형을 $2\times 1$ 과, $2 \times 2$ 타일로 채우는 방법의 경우의 수를 구한다.

우선 완전 탐색을 이용하여 모든 답을 만들어 개수를 만든 뒤, 여기에 메모이제이션을 적용하는 방법을 사용한다.

case 1 ( $2 \times 1$ )

case 2 ( $2 \times 1$ )
case 3 ( $2 \times 2$ )타일

맨 왼쪽 세로줄을 채우는 경우의 수는 다음 세가지를 고려한다. 이 세로줄은 1개의 타일로 덮여있을 수도 있고, case2와 같이 2개의 타일로 덮여있을 수도 있습니다.

위 3가지 방법은 타일링하는 방법을 모두 포함하며, 각각 독립적인 속성을 지니고 있습니다.

이를 따라가 규칙을 찾아보면 점화식은 아래와 같습니다

T(n) = T(n-1) + 2T(n-2)

아래는 위 점화식을 파이썬으로 구현한 코드입니다.

def tiling(n):
    if n == 0:
        return 1
    
    if dp[n] != 0:
        return dp[n]
    
    dp[n] = tiling(n-1) + tiling(n-2)*2
    return dp[n]

while True:
    try:
        dp = [0] * 300
        dp[1], dp[2] = 1, 3
        print(tiling(int(input())))
    except:
        break

무한루프에 예외처리를 한 이유는 해당 문제에서 입력은 여러 개의 테스트 케이스로 이루어져 있다. 라는 조건이 붙었기 때문에 채점을 할떄 임의로 종료하지 않기 위해서이다. (이러한 문제의 특성이라고 보면 된다.)

예시 2

같은 문제인데 범위만 늘어났다.
위에서 서술했듯이 정수 표현 범위가 넘어가서 10007로 나누어주라는 조건이 하나 더 붙었다.
이때는 dp를 적용할때 미리 모듈러연산을 적용한 뒤 저장해주면 된다. 코드는 아래와 같다.

def tiling(n):
    if n == 0:
        return 1
    
    if dp[n] != 0:
        return dp[n]
    
    dp[n] = (tiling(n-1) + tiling(n-2)*2) % 10007
    return dp[n]

dp = [0] * 1001
dp[1], dp[2] = 1, 3
print(tiling(int(input())))

경우의 수 계산하기 과정

모든 답을 직접 만들어서 세어보는 완전 탐색 알고리즘을 설계한다. 이때 부분문제는 아래의 속성이 성립해야 한다
1. 모든 경우는 이 선택지들에 포함됨
2. 어떤 경우도 두개 이상의 선택지에 포함되지 않음
최적화 문제를 해결할 때처럼 이전조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄인다. 재귀함수는 앞으로 남아있는 조각들을 고르는 경우의 수만을 반환해야 한다.
메모이제이션을 적용한다.