동적 프로그래밍 알고리즘 (1)

• 동적 프로그래밍 방법의 원리
  • 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법
    • 각 작은 문제는 원래의 문제와 동일한 문제이지만 입력의 크기만 작음
    • 입력의 크기가 아주 작은 단순한 문제가 되면 쉽게 해를 구할 수 있고, 이를 테이블에 저장
    • 이후 해당 소문제의 해가 필요할 때마다 테이블에 저장된 결과를 바로 이용
  • 동적 프로그래밍 => 동적 계획법
    • 컴퓨터에서의 프로그램과는 무관, 해를 구축하는 테이블을 이용한다는 의미
  • 최솟값/최댓값을 구하는 문제에 적용

 

• 최적화 문제에 동적 프로그래밍 방법을 적용하려면?
  • 최적성의 원리를 반드시 만족시켜야 함
    • 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다.
  • 동적 프로그래밍 방법의 처리 과정
    • 주어진 문제의 해에 대한 점화식
    • 가장 소문제 해를 구한 뒤 테이블
    • 테이블에 저장된 소문제의 해를 이용하여 해결
  • 분할 정복 방법 VS 동적 프로그래밍 방법
    • 하향식 / 상향식
    • 상위 레벨의 큰 문제를 순환적으로 부분 배열로 분할 및 합병 / 작은 소문제들을 모두 해결하여 해를 테이블에 저장한 후, 이 해들을 이용하여 보다 큰 크기의 문제 해결
    • 분할된 작은 문제들이 서로 독립적 / 중복되는 부분이 존재
    • 이진 탐색, 합병정렬, 퀵 정렬, 선택 문제 / 피보나치 수열, 연쇄 행렬 곱셈, 스트링 편집, 최단 경로
• 피보나치 수열 문제
  • f(n) = f(n-1) + f(n-2), n >= 2, f(0) = 0, f(1) = 1 -> 동적 프로그래밍 방법 O(n)
  • 분할 정복 방법을 적용하면?
    • 소문제가 독립이 아니기 때문에 계산이 비효율적
      • f(5) = f(4) + f(3) , f(4) = f(3) + f(2) 이처럼 f(3)이 중복됨... 비효율적
• 연쇄 행렬 곱셈 문제
  • n개의 행렬을 연쇄적으로 곱하는 경우
    • 결합 법칙의 성립 M1 x M2 x M3 = (M1 x M2) x M3 = M1 x (M2 x M3)
    • 여러 가지 다른 곰셈 순서가 존재 -> 곱셈의 횟수가 달라짐
  • 연쇄 행렬 곱셈 문제? 
    • 최소의 기본 곱셈 횟수를 가진 행렬의 곱셈 순서를 구하는 문제
    • (n,m) x (m,r) => n x m x r의 곱셈 횟수를 가진다.
  • 연쇄 행렬 곱셈 문제에서의 최적성의 원리
    • n개의 행렬을 곱하는 최적의 순서는 n개 행렬의 어떤 부분집합을 곱하는 최적의 순서를 포함
    • 동적 프로그래밍 방법으로 접근 가능
  • 점화식
    • n개의 행렬 M1 (d_(i-1) x d_i 차원 )
      • M1 x M2 x M3 x ... x M_(n-1) x M_n
    • C(i,j), 1<=i<=j<=n
      • M_i x M_i+1 x ... x M_j-1 x M_j 를 수행하는 데 필요한 곱셈의 최소 횟수
      • C(i,i) = 0
      • C(i,i+1) = d_i-1 x d_i x d_i+1 => 결과 행렬의 크기 : d_i-1 x d_i+1
      • C(i, i+2) = min{M_i x (M_i+1 x M_i+2) + 결합비용, (M_i x M_i+1) x M_i+1 + 결합 비용}
      • C(i,j) = min{ C(i,k) + C(k+1,j) + d_i-1 x d_k x d_j } ( i <= k <= j-1 )
  • 예)
    • M1 x M2 x M3 -> (M1xM2)xM3 vs M1x(M2xM3) [3x2, 2x4, 4x1 일때]
    • 테이블 채우기
    • 대각선 긴 순서로 채워나간다. 0 부터 채움
    • P[i][j] = j -> i부터 j까지 행렬을 곱할 때 최적의 순서로 갈라지는 지점이 k이다.
  • 성능 분석
    • O(n^3)
•  

Q4

C(4,6)은 M4×M5×M6을 수행하는 데 필요한 최소 곱셈 횟수를 의미한다. 3개의 행렬을 곱하는 경우에는 2가지 순서가 존재하며, 이때 필요한 기본 곱셈의 횟수는 다음과 같이 계산된다.(d0=5, d1=2, d2=3, d3=4, d4=6, d5=7 d6=8)

 

 

(M4M5)M6의 곱셈 횟수 = d3×d4×d5 + d3×d5×d6

= 4×6×7 + 4×7×8 = 168 + 224 = 392

 

M4(M5M6)의 곱셈 횟수 = d4×d5×d6 + d3×d4×d6

= 6×7×8 + 4×6×8 = 336 + 192 = 528

 

따라서 C(4,6)의 값은 min(392, 528)인 392가 된다.

 

Q5

연쇄 행렬 곱셈 알고리즘에서는 곱셈을 수행하는 데 최소 곱셈 횟수뿐만 아니라 최적의 곱셈 순서를 얻기 위해서 별도의 2차원 배열 P[][]를 사용하여, P[i][j]에는 i번째 행렬에서부터 j번째 행렬까지를 곱할 때 최소의 곱셈 횟수가 되도록 하는 k값이 저장된다. 따라서 P[i][j]의 값은 i부터 j까지 행렬을 곱할 때 최적의 순서로 갈라지는 기점을 나타낸다.

P[2][5]=3은 행렬 M2, M3, M4, M5를 곱하는 데 최적으로 순서로 갈라지는 기점이 3라는 의미로, M2M3과 M4M5로 갈라져서 곱셈을 수행한다.