8.11 경우의 수와 확률(1)_타일링 방법의 수 세기, 삼각형 위의 최대 경로 개수 세기(Python)

1. 예제 : 타일링 방법의 수 세기

문제 출처 : algospot.com :: TILING2

algospot.com :: TILING2

(1) 문제 분석

• 2*n 사각형을 채우는 모든 방법들은 맨 왼쪽 세로줄이 어떻게 채워져 있느냐로 나눌 수 있다.
• '한 개의 세로 타일에 의해 덮여 있는 방법'과 '두 개의 가로 타일에 의해 덮여 있는 방법'이 있다..
• 이 때, 다음의 조건이 성립함을 알 수 있다.
• 1. 이 두 가지 분류는 타일링 하는 방법을 모두 포함한다.
• 2. 두 가지 분류에 모두 포함되는 타일링 방법은 없다.
• 이 두 가지 속성은 경우의 수를 셀 때 항상 확인해야 하는 조건이다.
• 첫 번째 조건을 위반하면, 실제 수 보다 적은 답을 내놓는다.
• 두 번째 조건을 위반하면, 실제 수 보다 많은 답을 내놓는다.

 

• 각 단계에서 맨 왼쪽의 세로줄을 세로 타일 하나로 덮을 것인지 가로 타일 두 개로 덮을 것인지 결정하기만 하면 된다.
• 세로 타일 하나로 덮을 경우 남은 공간은 2*(n-1)이다.
• 가로 타일 두 개로 덮을 경우 남은 공간은 2*(n-2)이다.
• 따라서 다음과 같은 형태의 부분 문제를 정의할 수 있다.
• tiling(n) = 2*n 크기의 사각형을 타일로 덮는 방법

 

• tiling()이 한 번 호출될 때 할 수 있는 선택은 위의 설명대로 세로 타일 하나를 쓰느냐, 가로 타일 두 개를 쓰느냐를 생각하면 다음과 같은 점화식이 성립함을 알 수 있다. 
• tiling(n) = tiling(n-1) + tiling(n-2)

(2) 코드

# n = 100이면 64bit 정수형 표현 범위도 훌쩍 넘어가기 때문에 MOD로 나눈 값을 반환하기로 함
MOD = 1000000007

cache = [-1] * 101

def tiling(width):
    # 기저 사례 : width가 1 이하
    if width <= 1:
        return 1

    # 메모이제이션
    if cache[width] != -1:
        return cache[width]

    cache[width] = (tiling(width - 1) + tiling(width - 2)) % MOD
    return cache[width]

print(tiling(100))

• 여기서 n = 100이면 경우의 수는 64비트 정수형 표현 범위를 훌쩍 넘어가는 큰 값이기 때문에 MOD로 나눈 큰 값을 반환하는데 유의해야 한다.
• 부분 문제의 수는 O(n)이고 각각의 값을 계산하는데는 O(1)의 시간이 들기 때문에 전체 시간 복잡도는 O(n)이다.

---

github : Algorithmic_Problem_Soving_Strategies/code8_16.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies

---

2. 예제 : 삼각형 위의 최대 경로 개수 세기

문제 출처 : algospot.com :: TRIPATHCNT

algospot.com :: TRIPATHCNT

(1) 문제 분석

• 삼각형 위의 최대 경로는 한 가지 이상 나올 수 있다.
• 위 그림 왼쪽의 사각형을 기준으로 최대 경로는 [9, 7, 3, 5]와 [9, 7, 2, 6] 이렇게 2가지가 나온다.
• 이 문제를 해결하기 위해서는 오른쪽 그림과 같이 먼저 최적화 문제를 풀고, 각 부분 문제마다 최적해의 개수를 계산하는 동적 계획법 알고리즘을 만들어야 한다.
• 오른쪽 그림에서 (0, 0)에서 시작하는 최대 경로는 (1, 0), (1, 1) 중 어느쪽으로 내려가야 할 지 쉽게 알 수 있다.
• (1, 0)의 값인 13보다 (1, 1)의 값인 15가 더 크기 때문에 항상 (1, 1)로 내려가는 것이 이득이다.
• 따라서, (0, 0)에서 시작하는 최대 경로의 개수는 (1, 1)에서 시작하는 최대 경로의 개수와 같다.

 

• (1, 1)에서는 (2, 1)로 내려가든 (2, 2)로 내려가든 어느쪽으로 가든 최대 경로를 만들 수 있다.
• (2, 1)에서 시작하는 최대 경로와 (2, 2)에서 시작하는 최대 경로는 항상 (1, 1)에서 시작하는 모든 최대 경로에 포함 된다.
• 따라서 두 위치에서 시작하는 최대 경로의 합이 (1, 1)에서 시작하는 최대 경로의 개수가 된다.
• 이를 바탕으로 다음과 같은 부분 문제를 정의할 수 있다.
• count(r, c) = (r, c)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수
• 책에서는 (y, c)로 표기하지만 개인적으로 row(행)와 column(열)에서 따온 r과 c가 더 직관적으로 이해하기 쉬워서 바꿔 표기한다.

 

• (r, c)의 다음 칸은 최적화된 경로를 기준으로 어느쪽이 더 큰지 따라 결정된다.
• 부분 문제를 점화식으로 옮기면 다음과 같다.

• 여기서 path(r, c)는 (r, c)에서 최적화된 최대 경로의 값을 의미한다.

(2) 코드

cache = [[-1] * n for _ in range(n)]

def path(r, c):
    if r == n-1:
        return triangle[r][c]

    if cache[r][c] != -1:
        return cache[r][c]

    cache[r][c] = max(path(r + 1, c), path(r + 1, c + 1)) + triangle[r][c]
    return cache[r][c]

 

• 먼저, 삼각형의 최대 경로를 최적화하는 함수가 필요하다.
• 선택한 지점에서 나올 수 있는 최대 경로의 값을 반환한다.

countCache = [[-1] * 100 for _ in range(100)]

# (r, c)에서 시작해서 맨 아래줄까지 내려가는 경로 중 최대 경로의 개수를 반환
def count(r, c) :
    # 기저 사례 : 맨 아래줄에 도달한 경우
    if r == n-1:
        return 1

    # 메모이제이션
    if countCache[r][c] != -1:
        return countCache[r][c]

    countCache[r][c] = 0

    if path(r+1, c+1) >= path(r+1, c):
        countCache[r][c] += count(r+1, c+1)
    
    if path(r+1, c+1) <= path(r+1, c):
        countCache[r][c] += count(r+1, c)

    return countCache[r][c]

• 점화식에서 설계한 관계식을 코드로 구현한다.
• 특이 사항으로 점화식에서 path(r+1, c) == path(r+1, c+1)인 경우를 따로 조건문으로 설정하지 않고 두 가지 조건문에서 부등호 >=와 <=를 사용하여 어차피 같은 값인거 두 번 더해지도록 구현했다.

---

github : Algorithmic_Problem_Soving_Strategies/code8_9.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies

github : Algorithmic_Problem_Soving_Strategies/code8_17.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies