이거 혹시 DP로 풀 수 있는 문제인가?

• “프로그래밍” 은 테이블을 이용한 방법을 뜻한다. (컴퓨터와 관련이 없다.)
• 부분 문제의 해를 결합해 문제를 해결한다.
• 일반적으로 **최적화 문제(optimization problem)**에 적용한다.

최적화 문제

• 해와 값을 구분하자
  • 문제의 풀이를 “해(Solution)” 라 한다.
  • 그 풀이가 낸 답을 “값(Value)” 라 한다.
• 최적해는 각 해의 값 중 최적의 값을 내는 해이다.
• 최적의 값은 하나이지만 그 값을 내는 해는 여러개이다.
  • 최단 거리(값)를 크루스칼, 프림 등 여러 방법(해)으로 풀 수 있다.
• 즉 최적화 문제는 여러개의 해를 가진다.

분할정복과의 비교

• 분할 정복은 서로 겹치지 않는(disjoint) 문제를 부분 문제로 분할한다.
• DP는 부분문제가 서로 중복될 때(부분 문제끼리 부분문제를 공유) 적용할 수 있다.

공통점

• 문제를 부분 문제로 분할한다.
• 부분 문제를 활용해 전체 문제를 해결한다.

그리디와의 비교

• DP는 부분 문제들의 최적해를 먼저 구한 후 선택한다.
• 그리디는 작은 부분 문제를 모두 풀려고 하지 않고 “그리디 선택” 을 한 다음에 결과로 얻어진 부분 문제만을 푼다.

공통점

• 최적 부분 구조를 가지고 있다.

DP의 요소

• 어떤 문제에 적용해야 할까?
• 최적해의 구조를 확인해야 하는데, 해는 여러개일 수 있으므로 각 해중에 최적 부분 구조를 가지는 게 있는지 (나올때까지)일일히 확인해야 한다.
• 실제 적용에서는 이렇게 하는 것보다 문제의 정의 자체에서 최적 부분 구조가 보일 가능성이 높다.
  • 최단 경로, 최소 비용 등은 이미 최적 부분 구조가 있다는 것이 알려져 있다.

최적 부분 구조(Optimal substructure)

• 문제의 최적해가 그 안에 부분 문제의 최적해를 포함하고 있다.
  • 고려하고 있는 부분 문제가 최적해를 구하는 데 사용되는 부분 문제르 ㄹ모두 포함하고 있는지 확인해야 한다.
• 또한 이 부분 문제들이 서로 독립적이여야 한다.
  • 각 부분문제들이 자원을 공유하지 않아야 한다.
  • ex) 최장 경로는 부분 문제에서는 한 번 지난 경로를 다른 부분 문제에서 한 번 더 지날 수 있으므로 자원을 공유한 것이고 독립적이지 않다. → DP로 풀수 없다.

최적 부분 구조 확인

1. 문제에 대한 해는 선택하는 과정으로 만들어짐을 보임
2. 선택을 어떻게 하맂는 모르겠지만, 최적해에 이를 수 있는 선택이 주어졌다고 가정
3. 선택에서 발생하는 부분 문제가 어떤 것인지 정하고, 그 부분 문제의 범위를 잘 표현할 수 있는 방법을 정한다.
4. 한 개의 최적해에 사용된 부분 문제들의 해가 최적이어야 함을 증명한다.
   • “잘라 붙이기(cut-and-paste)” 방법을 이용한다.

최적 부분 구조의 구분

1. 원래의 문제에 대한 최적해는 몇 개의 부분 문제를 사용하는가
2. 원래 문제의 최적해에 사용할 부분 문제를 결정할 때 몇 가지 선택을 고려해야 하는가.

• 막대 자르기 문제 - 한개의 부분 문제, n(길이)가지 선택
• 행렬 곱 문제 - 두개 의 부분 문제(두개가 합쳐짐), j-i의 선택

잘라 붙이기 방법

• 각 부분 문제의 최적해가 아닌 부분을 잘라내고(cutting-out), 거기에 최적해를 붙이면(pasting-in) 원래의 해보다 좋은 해를 얻게 된다.

중복되는 부분 문제(Overlapping subproblems)

• 부분 문제들의 범위가 “작아야” 한다
• 재귀 알고리즘이 같은 문제를 계속해서 풀게 된다.
• 그리고 그 문제를 테이블에 저장한다.

DP를 푸는 4단계

1. 최적해의 구조의 특징을 찾는다. (최적해는 여러개가 될 수 있음에 주의)
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 일반적으로 상향식(bottom-up)방법으로 계산한다.
4. (필요한 경우)계산된 정보들로부터 최적해(최적값을 구한 방법)를 구성한다.

DP 구현의 두가지 방법

하향식(Top-down)

• 재귀로 푼다.
• 각 부분 문제의 결과를 배열이나 해시 테이블에 저장한다.(메모이제이션)
• 부분 문제 그래프를 깊이-우선 탐색 하는 것으로 볼 수 있다.

상향식(Bottom-up)

• 부분 문제의”크기”가 작은 것부터 올라간다.
• 부분 문제를 크기별로 정렬한=해야 한다.
• 특정 문제를 풀기 전에 그 해에 영향을 미치는 더 작은 부분 문제를 모두 풀어 그 해를 저장해놓는다.(타뷸레이션)
• 상향식이 하향식보다 함수 호출에 대한 오버헤드가 작다.(재귀는 계속 호출하므로)
  • 따라서 다 나은 상수 비율을 갖는다.
• 부분 문제 그래프를 위상 정렬의 역순으로 푼다고 볼 수 있다.

도움이 되는 개념

부분 문제 그래프

• 관련된 부분 문제의 집합과 부분 문제가 어떻게 연관되어 있는지 나타내는 그래프
• 하향식 재귀트리에서 같은 부분 문제를 한 정점으로 합친 그래프다.
• 각 정점은 부분 문제에 해당
• 간선은 한 부분 문제에 대해 해야할 선택

---

더 공부해봐야 할 것들

• 알고리즘 책에 나온 DP의 유명한 알고리즘들
  • 비터비 알고리즘 등

출처

• Introduction To Algorithms (3rd edition)