17, 18강 Dynamic Programming

• Dynamic Programming
  • 최적화 문제를 해결하는 방법 중 하나로, 문제를 더 작은 하위 문제로 나누어 해결하고, 그 결과를 Table에 저장하여 원래 문제를 해결하는 접근법입니다.
  • divide and conquar : 하위 독립적인 문제로 나눠 재귀적으로 해결함
  • Dynamic programming : 하위 문제가 독립적이지 않을 때, 적용 가능 → 딱 한 번 표를 만들어 그 다음부터 하위 문제가 발생할 때마다 표에서 꺼내서 사용
    • divide conquar은 발생할 때마다 계산해줘야함
• Dynamic Programming 과정(순서)
  1. 최적의 답의 구조를 특징화시킨다.
  2. 최적의 답의 값을 재귀적으로 정의한다.
  3. 최적의 답의 값을 bottom-up방식으로 계산한다.
  4. 계산된 정보로부터 최적의 답을 구축한다.(테이블화)
• Matrix multiplication으로 알아보자!
  • 행렬의 계산 결과 : A(pq) * B(qr) → C(q*r)
  • 행렬의 계산 cost : pqr

• 계산 예시

  • 어떤 순서로 병합하는지에 따라 계산 결과가 10배 빠르게도 차이 난다.

    • 왜? 어떤 변수가 행렬의 계산 결과에서 생략이 되느냐에 따라 다름

      

    • Ai = Pi-1*Pi의 차원의 행

  

  • 그렇다면 어디서 끊어서 계산을 해야할 것인가? k에서 끊어서 둘이 곱함
    • P(n)은 An까지 있을 때 행렬이 묶일 수 있는 경우의 수를 P(n)으로 나타냄

  

• Step1 Structure of an optimal solution (parenthesization 괄호치기 이용)

  • Ai~Aj까지 있을때 Ak를 기준으로 나눈다고 생각해보면,

    (Ai~k까지의 cost) + (Ak+1~j까지의 cost) + (Ai~k * Ak+1~j의 cost)가 전체 cost가 됨

  • Ai~k까지의 하위 parenthesization은 전체의 최적의 괄호치기가 되어야하고, Ak+1~j까지의 하위 parenthesization은 전체의 최적의 괄호치기가 되어야한다.

    • 즉, 문제에 대한 최적의 답은 하위 문제에 대한 최적의 답을 포함하고 있다.

    

    • 위의 말에 대한 부연설명임 → k = 2가 최적의 답이라고 가정하고 풀다가 k=3일때 더 우수한 답이 나온다면 k=2일때는 전체의 최적의 답이 될 수 없다!

• Step2 A recursive solution (재귀적 구현, 말만 재귀지 반복문으로 구현!)

  • Ai~Aj까지의 곱하기에 대한 minimum cost(계산 cost에 대한 minimum)을 저장할 수 있는 m[i, j]를 만듦

  • m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj

    • 결국 최솟값을 찾는 과정이므로 다음과 같이 정의할 수 있다.

    

  • 재귀는 많은 시간이 걸린다. 재귀는 각 재귀 트리의 다른 분기점에서 각각의 하위 문제들을 직면할 수 있다. → 중복되는 하위 문제는 동적 프로그래밍의 2번째 특징이다. (1번째는 최적의 답이 최적의 하위 구조를 포함하는 )

• Step3 Computing the optimal costs by bottom-up method

  • 테이블식, bottom up식의 방법을 사용
  • m[i, j] 배열을 채워가는(테이블을 만드는) 단계

  

  • 예시 m = 최소 cost / s = 최적의 cost는 어디서 split하면 될까?

    

    • 전체 테이블을 보면 이런식으로 작성하면 됌!
      • 아래에서부터 위로 채워나가는 방식이라 bottom up방식!

    

• Step4 Constructing an optimal solution

  • 최적의 cost와 그때의 split위치를 파악할 수 있게 되었으므로 어떤 순서로 행렬을 곱해야 최적의 값이 나오는지 알아보자!
  • s[i, n] = 1~n까지 행렬 곱셈시 최소 cost가 나오는 위치
  • 재귀함수를 이용해서 추적함

  

  • 예시 1~6일때

    • s[1~6] = 3 → s[1~3] , s[4~6] → (s[1~1],s[2~3]),(s[4~5],s[6~6]) →

      ((A1, (s[2~2],s[3~3])),((s[4~4],s[5~5]), A6)) → ((A1, (A2, A3)),((A4, A5), A6))

  

• 동적 프로그래밍의 요소

  • 최적의 구조 : 하위 최적의 구조를 포함한다.

    • 예를 들면 위의 테이블은 1~6(전체) 뿐만 아니라 1~4(sub하위)도 최적의 답을 도출해냈다.

  • 하위 문제의 중복 문제 : divide conquar은 중복되는 하위 문제를 계속 생성하여 실행시간이 다항적으로 늘어나는 반면, 동적 프로그래밍은 테이블을 이용함으로써 효율을 높일 수 있다.

    • 중복 문제를 피하려면 재귀적으로 이런식으로 수정하면 된다. (memoization)

    

• 최적의 구조에 대한 특징

  • 최적의 답을 위해 얼마나 많은 하위 문제가 사용되는가?
    • matrix multiplication을 예로 들면
      • Θ(n^2) → 테이블의 크기 (k에서 split하기 때문에) (테이블을 채워나가는 과정 생각)
  • 얼마나 많은 선택을 해야하는가?
    • k의 선택 범위 = j-i (n과 비슷) (어떤 k값에서 끊어야 cost가 제일낮을까?k번반복해봐야함)
  • 따라서 matrix multiplication의 시간 복잡도는 *Θ(n^2)O(n) = O(n^3)

• Recursive Procedure for Matrix-Chain Multiplication

  • m[1,n]을 계산하는 과정의 시간은 m[1,n]을 구성하는 하위 문제들의 걸린 시간을 모두 포함함
    • n단위로 지수함수적으로 나타날 것
      • substitution method로 증명

  

• Memoization 메모이제이션

  • 중복문제를 해결하는 효율적인 재귀함수의 접근 방식이다.
  • 동적프로그래밍과의 차이점
    • 동적프로그래밍은 bottom up을 사용한 반면, 메모이제이션은 top-down방식을 사용한다.
    • 동적프로그래밍은 모든 하위문제를 미리계산하여 테이블을 만드는 반면, 메모이제이션은 필요할 때 계산 후 결과를 저장한다. (필요하지 않은 문제는 계산 x → 효율성)
    • 하지만, 모든 하위 문제를 한 번 이상 해결해야 하는 경우엔 동적프로그래밍이 조금 더 유리하다.
      • 동적프로그래밍은 재귀를 위한 overhead가 없고, 테이블 유지를 위한 오버헤드가 적다.
      • 또, 동적 프로그래밍 알고리즘에서 테이블로 접근하는 게 유리한 문제들이 몇몇 있다.
  • pseudocode

  

  

• 동적프로그래밍에 대해 더 공부해보자

  • Longest Common Subsequence LCS 최장 공통 부분 수열

    • 두 수열에서 공통적으로 계속 증가하는 element들의 순서(연속적이지 않아도 됌)를 가진 수열을 의미한다.
    • 예시

    

    • 동적프로그래밍으로 구현

    

    • 3가지의 경우로 나온다. LCS(X,Y)로 부르면