[파이썬으로 배우는 알고리즘 기초] 3. 동적 계획법 (1)

3-0. 동적 계획법(Dynamic Programming)

• 문제를 더 작은 문제로 분할하되, 상향식으로 문제를 해결하는 방법
• 메모이제이션(Memoization): 가장 작은 입력 사례의 해답을 테이블에 저장하고 필요할 때 꺼내 쓰는 방법
• 1. 문제를 해결할 수 있는 재귀 관계식을 구함
  2. 가장 작은 입력사례로부터 상향식 방법으로 문제를 해결

---

3-1. 이항 계수

• 분할 정복법으로 구현 --- 중복으로 호출하게 됨

def bin(N, K):
    if K == 0 or N == K:
        return 1
    else:
        return bin(N - 1, K - 1) + bin(N - 1, K)

for N in range(10):
    for K in range(N + 1):
        print(bin(N, K), end=' ')
    print()

• 동적 계획법으로 구현
  1. 재귀 관계식
       B[i][j] = B[i -1][j - 1] + B[i - 1][j]     (0 < j < i)
                                      1                (j = 0 or j = i)
  2. 상향식 방법 --- 파스칼의 삼각형이 가진 특성 이용

def bin(N, K):
    B = [[0] * (K + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        for j in range(min(i, K) + 1):
            if j == 0 or j == i:
                B[i][j] = 1
            else:
                B[i][j] = B[i - 1][j - 1] + B[i - 1][j]
    return B[N][K]

for N in range(10):
    for K in range(N + 1):
        print(bin(N, K), end=' ')
    print()

• 동적 계획법으로 구현 --- 값이 대칭되는 성질 및 1차원 리스트 사용

def bin(N, K):
    if K > N // 2:
        K = N - K
    B = [0] * (K + 1)
    B[0] = 1
    for i in range(1, N + 1):
        j = min(i, K)
        while j > 0:
            B[j] = B[j] + B[j - 1]
            j -= 1
    return B[K]

for N in range(10):
    for K in range(N + 1):
        print(bin(N, K), end=' ')
    print()

---

3-2. 최단 경로(플로이드 알고리즘)

• 주어진 그래프에서 모든 정점의 쌍에 대한 최단 경로 구하기
• 그래프는 방향성, 가중치 그래프이고 최단 경로는 단순 경로로 같은 정점을 두 번 거치지 않음
• 최적화 문제: 하나 이상의 해답 후보가 존재하고, 해답 후보 중 가장 최적의 값을 가진 해답을 찾는 문제
• 1. 재귀 관계식
       D: 각 정점의 쌍이 가지는 최단 경로의 길이를 나타내는 행렬
       D[i][j]: vi에서 vj로 가는 최단 경로의 길이
       Dk: k개의 중간 정점을 지나는 최단 경로 길이 행렬
       Dk[i][j]: vi에서 vj로 k개의 중간 정점을 지나는 최단 경로 길이
     => 인접 행렬 W에서 최단 경로의 행렬 D와 재귀 관계식 구하기
  2. 상향식 방법
     초기화: D0 = W --- 다른 어떤 정점도 지나지 않는 최단 경로의 길이
     최종 목표: Dn = D --- 다른 모든 정점을 지날 수 있는 최단 경로의 길이
• D0 = W, Dk는 Dk-1로부터 구함(1 <= k <= n)
• Dk[i][j]는 하나의 정점을 더 지나도 새로운 최단 경로가 없는 경우 Dk-1[i][j]과 같음
  하나의 정점(vk)를 더 지나서 새로운 최단 경로가 있으면 Dk[i][j] = Dk-1[i][k] + Dk-1[k][j]

def floyd(W):
    D = W
    N = len(W)
    P = [[-1] * N for _ in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if D[i][j] > D[i][k] + D[k][j]:
                    D[i][j] = D[i][k] + D[k][j]
                    P[i][j] = k
    return D, P

def path(P, i, j):
    if P[i][j] != -1:
        path(P, i, P[i][j])
        print(f'v{P[i][j]} -> ', end='')
        path(P, P[i][j], j)

INF = 999
W = [
    [0, 1, INF, 1, 5],
    [9, 0, 3, 2, INF],
    [INF, INF, 0, 4, INF],
    [INF, INF, 2, 0, 3],
    [3, INF, INF, INF, 0]
]

D, P = floyd(W)
for line in D: # 최소 가중치 값
    print(*line)

for line in P: # 최단 경로
    print(*line)

start = 4
end = 2
print(f'shortest path from v{start} to v{end}: v{start} -> ', end='')
path(P, start, end)
print(f'v{end}')

 

 

 

※ 강의 링크: https://inf.run/v8Rn