2020-1ν•™κΈ°, λŒ€ν•™μ—μ„œ β€˜μ•Œκ³ λ¦¬μ¦˜β€™ μˆ˜μ—…μ„ λ“£κ³  κ³΅λΆ€ν•œ λ°”λ₯Ό μ •λ¦¬ν•œ κΈ€μž…λ‹ˆλ‹€. 지적은 μ–Έμ œλ‚˜ ν™˜μ˜μž…λ‹ˆλ‹€ :) 전체 ν¬μŠ€νŠΈλŠ” Algorithm ν¬μŠ€νŠΈμ—μ„œ ν™•μΈν•˜μ‹€ 수 μžˆμŠ΅λ‹ˆλ‹€.

3 minute read

2020-1ν•™κΈ°, λŒ€ν•™μ—μ„œ β€˜μ•Œκ³ λ¦¬μ¦˜β€™ μˆ˜μ—…μ„ λ“£κ³  κ³΅λΆ€ν•œ λ°”λ₯Ό μ •λ¦¬ν•œ κΈ€μž…λ‹ˆλ‹€. 지적은 μ–Έμ œλ‚˜ ν™˜μ˜μž…λ‹ˆλ‹€ :) 전체 ν¬μŠ€νŠΈλŠ” Algorithm ν¬μŠ€νŠΈμ—μ„œ ν™•μΈν•˜μ‹€ 수 μžˆμŠ΅λ‹ˆλ‹€.


일반적으둜 ν–‰λ ¬ κ³±μ…ˆ $A_1 \times A_2 \times \cdots \times A_n$은 Associative ν•˜κΈ° λ•Œλ¬Έμ— ν–‰λ ¬μ˜ κ³±μ…ˆ μˆœμ„œλ₯Ό μ–΄λ–»κ²Œ μ§„ν–‰ν•˜λŠλƒμ— λ”°λΌμ„œ 전체 μ—°μ‚°μ˜ μˆ˜κ°€ 달라진닀.

예λ₯Ό λ“€μ–΄,

  • $A: 50 \times 20$
  • $B: 20 \times 1$
  • $C: 1 \times 10$
  • $D: 10 \times 100$

4가지 행렬이 μžˆμ„ λ•Œ,

  • $A \times ((B \times C) \times D) = 120,200$
  • $(A \times B) \times (C \times D) = 7,000$

이 λœλ‹€. 즉, ν–‰λ ¬μ˜ κ³±μ…ˆ μˆœμ„œλ₯Ό 잘 μ‘°μ •ν•΄ ν•„μš”ν•œ μ—°μ‚°μ˜ 수λ₯Ό 쀄일 수 μžˆλ‹€λŠ” 것이닀!!


naive approach

κ°€μž₯ κ°„λ‹¨ν•˜μ§€λ§Œ, κ°€μž₯ λΉ„μš©μ΄ 많이 λ“œλŠ” 방법은 λͺ¨λ“  ν–‰λ ¬ κ³±μ…ˆ μˆœμ„œλ₯Ό λͺ¨λ‘ μ‚΄νŽ΄λ³΄λŠ” 것이닀. ν–‰λ ¬μ˜ κ³±μ…ˆμ€ binary operation이기 λ•Œλ¬Έμ— 전체 ν–‰λ ¬ 연산은 μ–΄λ–€ binary tree의 ν˜•νƒœλ‘œ ν‘œν˜„ν•  수 μžˆλ‹€. μ΄λ•Œ, μš°λ¦¬λŠ” $n$개의 행렬을 가지고 있기 λ•Œλ¬Έμ—, 이 binary treeλŠ” $n$개의 leaf nodeλ₯Ό 가진 νŠΈλ¦¬κ°€ λœλ‹€. λ˜ν•œ, κ·Έ κ°€μ§“μˆ˜λŠ” exponentially manyν•œ $2^n$κ°œκ°€ λœλ‹€.


Dynamic Programming

DPμ—μ„œλŠ” 이 문제λ₯Ό μ•„λž˜μ™€ 같이 μ ‘κ·Όν•œλ‹€.

"For a tree to be optimal, its subtree must also be optimal!"

λ‹€λ₯Έ κ³³μ—μ„œλŠ” λΆ€λΆ„μˆ˜μ—΄(sebsequence)을 μ΄μš©ν•΄ 문제λ₯Ό ν•΄κ²°ν•œλ‹€κ³ λ„ μ„€λͺ…ν•œλ‹€.

  1. 전체 μˆ˜μ—΄μ„ 길이 2의 λΆ€λΆ„ μˆ˜μ—΄λ‘œ λΆ„λ¦¬ν•œλ‹€.
  2. 길이 2의 λΆ€λΆ„ μˆ˜μ—΄μ—μ„œ (μ΅œμ†Œ) λΉ„μš©μ„ κ΅¬ν•œλ‹€.
  3. 길이 3의 λΆ€λΆ„ μˆ˜μ—΄μ„ μ‚΄νŽ΄λ³Έλ‹€. μ΄λ•Œ, 길이 2의 λΆ€λΆ„ μˆ˜μ—΄μ—μ„œ κ΅¬ν•œ λΉ„μš©μ„ λ°”νƒ•μœΌλ‘œ μ΅œμ†Œ λΉ„μš©μ„ κ΅¬ν•œλ‹€.
  4. 길이 4λŠ” 길이 3μ—μ„œ κ΅¬ν•œ μ΅œμ†Œ λΉ„μš©μ„ λ°”νƒ•μœΌλ‘œ μ΅œμ†Œ λΉ„μš©μ„ κ΅¬ν•œλ‹€.
  5. 이 과정을 길이 $n$κΉŒμ§€ 반볡

이 과정을 정리해 κΈ°μˆ ν•˜λ©΄,

  • $C(i, j)$ = min cost of multiplying $A_i \times \cdots A_j$

for $\ell = 1, 2, \dots, n$
  for $i=1, 2, \dots, n - \ell + 1$
    $j = i + \ell$
    for $k=i, \dots, j-1$
      $\texttt{cost} = C(i, k) + C(k+1, j) + m_{i-1} \times m_k \times m_j$
      $C(i, j) = \min \{ C(i, j), \; \texttt{cost}\}$

return $C(1, n)$

μœ„μ˜ 과정을 그림으둜 ν‘œν˜„ν•˜λ©΄ μ•„λž˜μ™€ 같이 ν‘œν˜„ν•  수 μžˆλ‹€.

Image from here

λ§Œμ•½ best-split μˆœμ„œλ₯Ό 기둝해 μ‹€μ œ binary opr treeλ₯Ό κ΅¬μ„±ν•˜κ³  μ‹Άλ‹€λ©΄, $C(i, j)$λ₯Ό κ°±μ‹ ν•˜λŠ” κ³Όμ •μ—μ„œ μ–Έμ œ minimum을 λ‹¬μ„±ν•˜λŠ”μ§€ 기둝해두면 λœλ‹€.

      if $\texttt{cost} < C(i, j)$
        $C(i, j) = \texttt{cost}$
        $S(i, j) = k$

그리고 binary opr treeλ₯Ό μž¬ν˜„ν•  λ•ŒλŠ” $S(1, n)$으둜 splitting pointλ₯Ό μ°Ύκ³ , 그리고 $S(1, k)$, $S(k, n)$의 κ°’μœΌλ‘œ κ·Έ λ‹€μŒ splitting point을 μ°Ύκ³ , … 이런 μ‹μœΌλ‘œ μ§„ν–‰ν•˜λ©΄ λœλ‹€ 😁


μΆ”μ²œ 문제


참고자료