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

동적 프로그래밍 알고리즘

• 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고, 이를 이용하여 크기가 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법이다.
  → 최적화문제(최솟값, 최댓값을 구하는 문제)에 적용된다.
• 분할 정복 방법과의 차이점
  분할 정복 방법은 하향식 접근 방법이고, 동적 프로그래밍은 상향식 접근 방법이다.
  분할 정복 방법의 분할된 작은 문제들은 서로 독립적이지만 동적 프로그래밍 방법의 소문제들은 서로 독립되지 않고 중복되는 부분이 존재한다.
• 주요 알고리즘
  피보나치 수열, 연쇄 행렬 곱셈, 스트링 편집 거리, 모든 정점 간의 최단 경로(플로이드 알고리즘), 저울 문제
• 조건
  최적성의 원리(주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다)를 반드시 만족해야한다.
• 적용과정
  1. 최적성의 원리가 성립되는지 확인
  2. 주어진 문제에 대해 최적해를 제공하는 점화식을 도출
  3. 가장 작은 소문제부터 점화식의 해를 구해서 테이블에 저장
  4. 테이블에 저장된 소문제의 해를 이용하여 점차적으로 큰 상위 문제의 해를 구함

피보나치 수열

• 순환 형태를 이용한 분할 정복 방법으로 계산하게 되면 소문제가 독립적이지 아니므로 중복된 계산이 필요하게 되여 매우 비효율적이다.
• 동적 프로그래밍 방법을 이용하여 계산하면 시간복잡도는 O(n) 이다.

연쇄 행렬 곱셈 문제

• n개의 행렬을 연쇄적으로 곱하는 경우(곱하는 순서가 유지되는 경우) → 결합법칙이 성립된다 → 여러가지 다른 곱셈 순서가 존재하게 된다. → 연산에 필요한 곱셈의 순서가 달라지게 된다.
• 정의
  n개의 행렬을 연쇄적으로 곱할 때 최적의 곱셈 순서를 구하는 문제(최소의 곱셈 횟수)
• 최적성의 원리
  n개의 행렬을 곱하는 최적의 순서는 n개의 행렬의 어떤 부분집합을 곱하는 최적의 순서를 포함한다. 예를 들어 7개의 행렬을 곱할 때 부분 행렬의 곱하는 최적의 순서를 구하여 이 최적해를 이용하여 전체를 구할 수 있게 된다.
• 점화식 도출
• 성능
  O(n ** 3)