Dynamic Programming is Blind

• 보이지 않는 것들을 여러가지 방법으로 푼다는 것을 의미한다.
  • Matrix chain multiplication: O(n^3)
  • Longest common subsequences: O(mn)
  • Optimal binary search trees: O(n^3)
• Why?
  • optimal solution을 계산하기 위한 많은 선택들이 있다.
  • DP는 이것들을 다 선택한다 (exhaustively, blindly)

Example: MCM

• 어떤 선택이 가장 좋은 선택인지, 어떤 선택은 할 필요가 없는 것인지 알아야 한다.
• Greedy algorithm;
  • 어떤 것이 가장 좋은 선택인지 결정하도록 함.

Greedy algorithm

• 몇몇 optimization problem에 대한 디자인 전략
• 그 순간에 가장 best라고 느껴지는 선택 — local optimum
• 항상 globally optimum solutions로 이끄는 것은 아니다.
• 많은 경우에 대해서 global optimum으로 이끈다.

Coin change

• 가장 적은 수의 coins로 거슬러 주고 싶은 경우
• Algorithm: 그 다음으로 많은 코인이 가지고 있는 가격을 선택한다.
• Example
  • coins = {half-dollar, quarter, dime, nickel, penny}
  • 74cents = 1(half-dollar)+2(dime)+4(penny)

Activity-Selection Problem

Problem: 놀이공원에서 가성비를 뽑자!

• 많은 놀이기구들은, 각각 시작하는 시간과 끝나는 시간이 다르다.
• Your goal: 가장 많은 놀이기구를 타는 것
  • 스케줄링을 잘해야 함.
  • 여기서는 다루지 않지만, 놀이기구를 타는 시간을 제일 많이 하는 경우도 있음
• Welcome to the activity selection problem