동적프로그래밍 알고리즘

• 동적프로그래밍
  • 동적프로그래밍 방법의 원리
    • 문제의 크기가 작은 소문제에 대한 해를 저장해놓고, 이를 이용해서 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근방법
      • 각각의 소문제는 원래의 문제와 동일하지만 입력의 크기만 줄어듦
      • 입력의 크기가 아주작은 단순한 문제가 되면 쉽게 해를 구할 수 있고 이런 소문제의 해는 다시 사용될 수 있으므로 테이블에 저장
      • 해당 소문제의 해가 필요할 때마다 테이블에서 결과를 바로 이용
    • 동적 프로그래밍(동적 계획법)
      • 해를 구축하는 테이블을 이용함
      • 최적화 문제에 사용됨(최소값, 최대값 찾기)
    • 분할 정복 방법
      • 하향식 접근 방법
      • 상위 레벨의 큰 문제를 순환적으로 부분배열로 분할하고 이들의 해를 결합해서 원래 문제의 해결하는 방법
      • 분할된 작은 문제들은 서로 독립적
      • 이진탐색, 합병정렬, 퀵정렬, 선택문제
    • 동적 프로그래밍 방법
      • 상향식 접근 방법
      • 입력 크기가 작은 소문제들을 모두 해결해서 구한 해를 테이블에 저장한 후 이 해들을 이용하여 보다큰 크기의 문제를 해결하는 방법
      • 소문제들은 서로 독립적이지 않고 중복되는 부분이 존재
      • 피보나치 수열, 연쇄행렬곱셈, 스트링편집거리, 모든 정점간의 최단경로, 저울문제
    • 동적 프로그래밍 방법을 적용하려면?
      • 최적성의 원리를 반드시 만족해야함
        • 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다
    • 동적 프로그래밍 방법의 적용과정
      • 문제의 특성을 분석하여 최적성의 원리가 성립되는지 확인
      • 주어진 문제에 대해 최적해를 제공하는 점화식을 도출
      • 가장 작은 소문제부터 점화식의 해를 구해서 테이블에 저장
      • 테이블에 저장된 소문제의 해를 이용하여 점차적으로 큰 상위 문제의 해를 구함
• 피보나치 수열문제
  • 개념과 원리
    • 피보나치 수열
      • f(n) = f(n-1) + f(n-2), n>=2, f(0) = 0, f(1) = 1
  • 특징
    • 순환 형태를 이용한 피보나치 수열 f(5) 계산의 구조도
    • 소문제가 독립이 아니므로 중복된 계산이 필요 -> 매우 비효율적
• 연쇄 행렬 곱셈 문제
  • n개의 행렬을 연쇄적으로 곱하는 경우
    • 결합법칙 성립
      • 여러 가지 다른 곱셈순서가 존재
        • 연산에 필요한 곱셈의 횟수가 달라짐
  • n개의 행렬을 연쇄적으로 곱할 때 최적의 곱셈순서를 구하는 문제
    • 최적의 곱셈순서 -> 최소의 기본 곱셈 횟수를 갖는 행렬의 곱셈 순서
  • n개의 행렬을 곱하는 최적의 순서는 n개의 행렬의 어떤 부분집합을 곱하는 최적의 순서를 포함
    • 7개의 행렬을 곱하는 최적의 순서: (M1M2)((((M3M4)M5)M6)M7)
      • M3, M4, M5를 곱하는 최적의 순서 -> ((M3M4)M5)
      • 부분 문제들의 최적해로 n개 행렬을 곱하는 최적의 순서를 구할 수 있음
      • 최적성의 원리를 만족
      • 동적 프로그래밍 방법으로 해결 가능
  • 점화식 도출
    • n개의 행렬 Mi(di-1*di차원) (1<=i<=n)
    • C(i, j) 1<=i<=j<=n
      • Mi*Mi+1*Mi+2*...*Mj-1*Mj를 수행하는 데 필요한 곱셈의 최소 횟수
    • C(i, i) = 0, 1 <= i <= n
    • C(i, i+1) = di-1*di*di+1
    • ...
    • 일반화된 점화식
      • C(i,j) = min i <= k <= j-1 {(Mj ... Mk)(Mk+1 ... Mj)+결합비용} = min i<=k <=j-1 {C(i, k)+C(k+1,j)+di-1dkdj}
    • 최적의 곱셈 순서
      • P[i][j] = k
        • i부터 j까지 행렬을 곱할 때 최적의 순서로 갈라지는 지점이 k이다
         

•  
  • 성능: O(n^3)