1. Dynamic Programming

• 문제의 일부분을 해결한 후 그 결과를 재활용하는 방법
  • 분할정복과 유사함
• 예시: 이진 검색, 최단경로 알고리즘, 최적화 문제 등
• 분할정복과의 차이점
  • 분할정복:
    • 분할된 서브문제가 독립적
    • 서브문제가 다르기 때문에 메모이제이션 활용할 수가 없음
  • DP:
    • 문제를 분할하는 경우 중복되는 서브 문제가 있음
    • 서브문제가 같은 경우 메모이제이션(=변수를 통해 메모하고, 메모한 변수를 재사용하는 것)을 활용해 같은 문제를 해결할 수 있음
    • DP를 활용하면 해결 가능한 문제 범위가 확대됨

좌: DP, 우: 분할정복

• DP는 분할정복에서 ‘중복되는 서브문제'와 ‘최적 부분 구조'라는 개념이 추가됨

  • 중복되는 서브문제: 메인과 서브문제를 같은 방법으로 풀 수 있어야 함
  • 최적 부분 구조: 메인문제의 해결방법을 서브문제에서 구해 재사용하는 구조여야 함

  → 따라서 DP는 최적 부분 구조로 구성된 중복 서브 문제를 분할정복으로 해결한다

• DP의 두 가지 방법론

  • 메모이제이션(하향식 방법): 메인문제를 분할하여 해결
  • 태뷸레이션(상향식 방법): 가장 작은 문제를 먼저 해결하고 마지막으로 메인문제 해결

2. Greedy

• DP : 중복되는 서브문제 ↔ Greedy : 중복되지 않는 서브문제

• 발견법 중 하나

  • 발견법: 최선/최적을 답을 찾기 보다는 주어진 상황을 한단계씩 빠른 시간 내에 해결하기 위해 사용하는 방법론
    • 역추적과 같이 알고리즘 수행시간이 오래 걸릴 때 사용

• Greedy는 역추적과 다르게 다른 문제들과 독립적

  • 예) 짐싸기, 여행 경로 짜기 등

• 예시

  

  1. 1번노드에서 비용이 적은 2번노드(1의 비용)로,

  2. 2번노드에서 비용이 적은 4번노드(3의 비용)로,

  3. 4번노드에서 비용이 적은 3번노드(2의 비용)로,

  4. 3번노드에서 비용이 적고 목적지인 6번노드(2의 비용)로 이동

  ⇒ 총 비용: 8

  • 각 노드별 이동비용을 고려할 때, 최소비용과 최단경로가 모두 고려된 방법은 아닐 수 있음

DP와 Greedy

• 최적 부분 구조 문제를 푼다는 점에서 비교할 때
  • DP
    • 문제를 작은 단위로 분할하여 해결한 후, 해결된 중복문제들의 결과를 기반으로 전체문제를 해결
  • Greedy
    • 각 단계마다 최적해를 찾는 문제로 접근
    • 해결해야 할 전체문제의 갯수를 줄이기위해 개별적으로 문제를 해결해나감