[CM301] 10. 동적 계획법 II (Dynamic Programming II)

게시 2026/01/13 업데이트 2026/01/24

17 분정도 걸립니다

[CM301] 10. 동적 계획법 II (Dynamic Programming II)

이전 내용에 이어서 동적 계획법의 예시들을 살펴볼텐데, 이번에는 그래프와 관련된 문제들에 대해 다뤄보겠습니다.

행렬의 곱셈

크기 $p \times q$, $ q \times r$의 두 행렬 $A$, $B$가 있을 때 행렬의 곱 $AB$는 $O(pqr)$의 시간이 걸립니다.

  
def matmul(A[p * q], B[q * r]):
  C = []  # p * r 크기의 행렬
  
  for i: 1 to p:
    for j: 1 to r:
      C[i, j] = 0
      for k := 1 to q:
        C[i, j] += A[i, k] * B[k, j]
        
  return C

그런데 이 행렬 곱셉이 연속으로 존재한다면, 어떤 행렬을 먼저 곱할 것인지에 따라 총 실행시간이 달라집니다.

행렬	$A$	$B$	$C$	$D$
크기	$50 \times 20$	$20 \times 1$	$1 \times 10$	$10 \times 100$

$A \times ((B \times C) \times D)$ : 20 * 1 * 10 + 20 * 10 * 100 + 50 * 20 * 100 = 120200
$(A \times (B \times C)) \times D$ : 20 * 1* 10 + 50 * 20 * 10 + 50 * 10 * 100 = 60200
$(A \times B) \times (C \times D)$ : 50 * 20 * 1 + 1 * 10 * 100 + 50 * 1 * 100 = 7000

그래서 계산 시간을 최소로 하도록 행렬의 곱셈 순서를 정하는 것이 중요한데, 이것도 동적 계획법으로 해결할 수 있습니다. 행렬들이 괄호로 묶이는 모습은 이진 트리로 나타낼 수 있는데, 여기서 하나의 큰 트리는 두 개의 하위 트리로 나뉠 수 있습니다.

각 크기가 $m_{i-1} * m_i, m_i * m_{i+1}, …, m_{j-1} * m_j$인 행렬 $A_i, … , A_j$의 최소 실행시간을 $C(i, j)$라고 합시다. 이들을 두 개의 하위 트리로 나눈 뒤, 하위 트리를 모두 곱한 두 행렬의 곱셈 시간을 더하면 됩니다.

\[C(i, j) = \min_{i \leq k \leq j} \{ C(i, k) + C(k+1, j) + m_{i-1} * m_k * m_j \}\]

  
def chain_matmul(m[0, ..., n]):
  for i := i to n:
    C[i, j] = 0
  
  for s := 1 to n-1:
    for i := 1 to n-s:
      j = i + s
      for k := i to j-1:
	      C[i, j] = min(C[i, j], C[i, k] + C[k+1, j] + m[i-1]*m[k]*m[j])
	
	return C[1, n]

실행시간은 $O(n^3)$입니다.

최적화된 이진 탐색 트리

이진 탐색 트리는 왼쪽의 자식이 부모보다 작은 값을, 왼쪽의 자식이 부모보다 큰 값을 가지도록 이진 트리를 구성하여 탐색에 사용하는 방법입니다.

이진 탐색 트리는 서로 다른 모양이 둘 이상 존재하는데, 당연히 모양에 따라 각 요소에 접근하는 시간도 달라집니다. 그래서 자주 쓰이는 요소가 있으면 의도적으로 루트와 가깝게 배치하는 방식으로 나름의 최적화가 가능합니다. 이제 요소 $k_i$와 빈도 $p_i$가 주어졌을 때, 평균 탐색 시간을 최소로 하는 이진 탐색 트리를 구성해야 합니다.

요소 $k_i, …, k_j$로 이루어진 이진 탐색 트리의 최소 평균 탐색 시간을 $e(i, j)$라고 합시다. 만약 이 트리가 어떤 요소의 하위 트리로 들어간다면, 모든 노드는 깊이가 1 증가합니다. 그 말은 즉 $e(i, j)$도 같이 증가한다는 것인데, 각 노드의 빈도를 한 번씩 더 더하면 되겠죠? 이 증가값을 $w(i, j)$라고 합시다. 그러면

\[w(i, j) = \sum_{i \leq x \leq j} p_x\]

이제 이 트리에서 어떤 노드가 루트자리에 있는지 생각해봅시다. 어떤 노드 $i \leq r \leq j$가 루트에 있다고 가정합니다. 루트 자신은 $p_r$의 탐색시간을 가지며 왼쪽 하위 트리는 $e(i, r-1) + w(i, r-1)$, 오른쪽 하위 트리는 $e(r+1, j) + w(r+1, j)$의 탐색 시간을 가집니다. 즉,

\[e(i, j) = e(i, r-1) + w(i, r-1) + e(r+1, j) + w(r+1, j) + p_r\] \[= e(i, r-1) + e(r+1, j) + w(i, j)\]

의 하위 문제로 나타낼 수 있습니다. 남은 일은 모든 $r$을 돌면서 최솟값을 찾아내는 것 뿐입니다.

\[e(i, j)=0 \quad (\text{if} \; i = j-1)\] \[e(i, j) = \min_{i \leq r \leq j} e(i, r-1) + e(r+1, j) + w(i, j) \quad (\text{if} \; i \leq j)\]

  
def optimal_bst_dp(p[1, ..., n]):
  e = []  # 탐색 시간
  w = []  # 하위 트리로 내릴 때 탐색 시간 증가량
  
  for i := 1 to n+1:
    e[i, i-1] = 0  # 빈 트리
    w[i, i-1] = 0  # 빈 트리
    
  for l := 1 to n:
    for i := 1 to n-l+1:  # 처음부터 l칸 전 까지
      j = i+l-1  # [i, j] 구간의 크기는 l로 고정
      e[i, j] = infinite  # 초기화
      w[i, j] = w[i, j-1] + p[j]  # w도 dp로 계산
      
      for r := i to j:  # 하위 트리의 모든 요소에 대해
        t = e[i, r-l] + e[r+1, j] + w[i, j]  # r을 기준으로 두 개 트리로 나눔
          if t < e[i, j]:  # 만약 e[i, j]보다 더 작다면
            e[i, j] = t  # 갱신
            root(i, j) = r  # 현재 트리의 루트는 r
  
  return e, root

실행시간은 $O(n^3)$입니다.

플로이드-와셜 알고리즘 (Floyd-Warshall Algorithm)

잠시 시간을 되감아 최단 경로를 구하던 때로 돌아가봅시다. 우리는 음의 가중치까지 해결할 수 있는 벨만-포드 알고리즘에 대해 살펴보았습니다. 실행시간은 $O(|V||E|)$로, 시간은 조금 걸리지만 확실한 방법이었죠.

그런데, 이걸 모든 점에 대해 수행해야 한다면… 이야기가 조금 달라지겠죠? $T(|V|) = |V|O(|V||E|)$ 이니까, 자그마치 $O(|V|^4)$의 시간이 걸립니다. 그래서 이것도 동적 계획법으로 풀어보도록 하겠습니다.

점 $i$에서 $j$까지, 점 ${1, 2, …, k}$만 사용해서 도달할 수 있는 가장 짧은 경로의 길이를 $\text{dist(i, j, k)}$라고 합시다. 이 경로는 점 $k$를 지나는 경우와 그렇지 않은 경우 두 가지 중 하나에 해당할 것입니다.

점 $k$를 지나는 경우, $i$에서 $k$까지의 경로와 $k$에서 $j$까지의 경로로 나눌 수 있습니다. 이들은 모두 $k$를 지나지 않으므로, 최단 경로의 길이를 이렇게 쓸 수 있습니다.

\[\text{dist}(i, k, k-1) + \text{dist}(k, j, k-1)\]

$k$를 지나지 않는 경로 또한 당연히 이렇게 쓰게 됩니다.

\[\text{dist}(i, j, k-1)\]

따라서, 우리는 이 두 하위 문제 중 더 짧은 것을 선택하면 됩니다.

  
def Floyd_Warshall(G=(E,V): Graph):
  for i := 1 to n:
    for j := 1 to n:
      dist(i, j, 0) = infinite  # 기본값
  
  for e=(i, j) in E:
    dist(i, j, 0) = l(i, j)  # 바로 연결된 점은 선의 가중치만큼 길이를 가짐
  
  for k := 1 to n:
    for i := 1 to n:
      for j := 1 to n:
        # k를 지나는 경우와 지나지 않는 경우를 비교
        dist(i, j, k) = min(dist(i, k, k-1) + dist(k, j, k-1) + dist(i, j, k-1))
  
  return dist

실행시간은 $O(n^3)$입니다.

순회 세일즈맨 문제 (Traveling Salesman Problem, TSP)

여러분이 외판원이 되어 도시들을 돌아다니며 영업을 뛴다고 생각해봅시다. 도시는 서로 복잡하게 연결되어 있으니까, 한 도시에서 다른 도시로 이동하는 방법은 여러가지가 있을 것입니다. 그리고 시간이 곧 효율이고 생명이죠. 가능한 짧은 시간 안에 도시들을 모두 방문하고 시작점으로 복귀하고자 합니다.

$n$개의 점이 있고 두 점 $i$와 $j$가 거리 $d_{ij}$만큼 떨어져 있을 때, 모든 지점을 한 번씩만 방문하여 돌아오는 최단 경로를 구하는 문제를 순회 세일즈맨 문제(Traveling Salesman Problem, TSP)라고 합니다.

정말 간단하게 생각해서, 모든 경우의 수를 직접 비교해보면 어떨까요? 최악의 경우라면 모든 점들이 연결된 밀집 그래프일 때입니다. 이 경우, 서로 다른 $n$개의 점을 줄 세우는 것과 같으므로, 자그마치 $O(n!)$의 시간이 필요하게 됩니다. 이때까지 나온 다항식 시간들과는 비교도 안 되죠.

TSP도 동적 계획법으로 해결해보겠습니다. 점 ${ 1, …, n }$이 주어져 있을 때, 점 $1$에서 출발해 모든 점을 한 번씩 지나 $j \neq 1$에 도착하는 최단 경로의 길이를 $C(S, j)$라고 합시다.

기본 경우는 $j=1$일 때 입니다. 이는 또 다시 두 가지로 나눌 수 있습니다.

경우 1. $S = {1}$ 뿐이며 $j=1$ : 주어진 점이 1, 도착점도 1이므로 경로의 길이는 0입니다.
경우 2. ${1} \subset S$ 이며 $j=1$ : $j \neq 1$라고 정했으므로, 길이는 모두 무한입니다.

이제 점의 개수가 2개 이상이면서 도착점도 $j \neq 1$인 경우를 생각해봅시다. 이 때 $j$ 바로 이전에 올 수 있는 점 $i$가 존재할 것입니다. 만약 1에서 출발해 $i$에 도착하는 하위 문제를 푼다면, 거기에 $d_{ij}$을 더한 값들을 비교해 최솟값을 선택할 수 있습니다. 따라서, 우리는 $C(S, j)$를 이렇게 정의할 수 있습니다.

\[C(\{1\}, 1) = 0, \; C(S, 1) = \infty\] \[C(S, j) = \min_{i \in S, \; i \neq j} \{ C(S - \{ j \}, i) + d_{ij} \}\]

다만, 이렇게 답을 찾으면 한 가지가 빠져 있다고 생각할 수 있습니다. 우리가 구한 경로는 1이 아닌 다른 점에서 끝나는 경로, 즉 회로가 아니니까요. 문제는 외판원이 다시 시작점으로 돌아오는 것을 전제로 하고 있습니다.

그래서 마지막으로 답을 반환하기 전에, 우리는 모든 종착점 $j$에 대해 그 최단경로에 $j$와 1 사이의 거리를 더해 회로의 총 길이를 계산해야 합니다. 그리고 그중에서 가장 짧은 경로를 가지는 $j$를 고르는 것이죠.

\[\min_j \{ C(\{ 1, …, n \}, j) + d_{j1} \}\]

  
def TSP_dp(G=(d,v): Graph, n):
  V = {1, ..., n}  # 점들의 집합
  C({1}, 1) = 0  # 기본 경우 1.
  
  for s := 2 to n:
    X = []  # 크기 s 이면서 1이 포함된 부분집합들
    for i subset V:
      if i.size == s and (1 in i):
        X.push(i)
    
    for S in X:  # 크기 s 이면서 1이 포함된 부분집합 
      C(S, 1) = infinite  # 기본 경우 2.
      
      for j in S - {1}:  # 1이 아닌 다른 점 j
        for i in S - {j}:  # 1도 j도 아닌 중간 점 i
          # 각 i 경우에 대해 비교
          C(S, j) = min(C(S, j), C(S - {j}, i) + d(i,j))
  
  return min(C(N, j) + d(j, 1), j := 1 to n)

집합 $S$는 전체 $n$개 지점의 부분집합입니다. 여기서 도착점이 되는 $j$를 제외하면 $n-1$개 이므로, 최대 $2^(n-1)$개의 $S$가 존재할 수 있습니다. 선택할 수 있는 $j$는 1을 제외하여 $n-1$가지 입니다. 따라서, 발생하는 하위 집합의 총 개수는 $(n-1)*2^(n-1) = O(n*2^n)$입니다.

그리고 하나의 하위문제마다 자신의 이전 점 $i$를 모두 비교해야 하는데, 크기 $n$의 하위문제에서 가능한 $i$의 개수는 $n-2$개 이므로 하위문제당 실행시간은 $O(n)$입니다.

따라서, 전체 실행시간은 $O(n^2 * 2^n)$입니다.

cm301

알고리즘

행렬의 곱셈

최적화된 이진 탐색 트리

플로이드-와셜 알고리즘 (Floyd-Warshall Algorithm)

순회 세일즈맨 문제 (Traveling Salesman Problem, TSP)

인기 태그