그리디 알고리즘 (Greedy)과 다이나믹 프로그래밍 (DP)

그리디

여러 경우 중 하나를 선택할 때마다 그 순간에 최적인 해를 선택해 나가는 근시안적인 방법이다.

특징

• 각 선택 시점의 결정이 지역적으로 최적이고, 그 결정들이 모여 만든 답이 최적해라는 보장이 있어야 사용가능하다.
• 이미 선택한 결정은 번복하지 않기 때문에 대부분의 단순하며 제한적인 문제들에 적용된다.

두 가지 필수 요소

1. Greedy choice property: 탐욕적 선택 속성

• 탐욕적 선택이 최적해로 갈 수 있음을 보이고 탐욕적 선택이 항상 안전하다는 것을 확인해야 한다

    2. Optimal substructure property: 최적 부분 구조

• 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남아야 한다.

==> 원 문제의 최적 해 = 탐욕적 선택 + 하위 문제의 최적 해

 

---

DP

‘귀납법’을 만족하는 점화식을 찾아 Recursive & Memoization을 활용해 문제를 해결하는 방식.

• Memoization: 이전에 계산한 값을 메모리에 저장해 중복 계산을 줄여 실행 속도 개선하는 기술
• 그리디와 비슷하게 최적화 문제를 해결하는 알고리즘이다.

두 가지 필수 요건

1. Optimal substructure: 최적 부분 문제 구조

• 최적화의 원칙: 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다.

    2. Overlapping subproblems: 중복 부분 문제 구조

• 이전에 계산된 작은 문제의 해가 다른 문제에서 필요하게 되는데(Overlapping subproblems) 이를 위해 이미 해결된 작은 문제들의 해들을 어떤 저장 공간에 저장하여 별도의 과정 없이 필요할 때 참조할 수 있다.