개념

• 각 단계의 지역적 최적 해가 궁극적으로 전역 최적 해가 되는 것을 말한다.
  • 쉽게 말하면 xx는 ~~ 를 하면 답을 찾을 수 있을 것이다 라는 과정을 찾는 것이다.
• 그리디는 최대한 나중에 접근하는 방법으로 남기는 것이 좋다.
  • 처음에는 완전탐색 → 시간복잡도에 막히면 DP → 그것도 안된단 판단이 서면 그리디를 써보자.
• 생각했던 최적 해를 찾는 방식이 그 지역에는 적용될 수 있으나, 전역 최적해를 찾는데는 맞지 않을 수 있다.
  • 이럴 경우 재빠르게 버리고 다른 방식을 찾아야 한다.

그리디의 조건

• 최적 부분 구조를 가지고 있어야 한다.
  • 문제를 여러 단계로 나누고, 각 단계에서 최적의 선택을 할 시 전체 문제에 대한 최적해를 얻을 수 있다는 논리로 접근한다.
  • 참고로 DP 또한 비슷한 논리를 사용하는데, 이 경우 하위 문제의 해를 저장하고 재사용하여 효율적으로 최적해를 찾는 방식을 쓴다
• 탐욕적 속성이 증명되어야 한다.
  • 현재 idx에서 가장 효율적일 것 같은 최적해를 찾는다.
    • 과거 시점의 idx에서의 선택은 현재의 선택과는 연관이 없다. 현재 상태에 집중한다.
  • 보통 정렬이나 우선순위 큐를 사용하는 경우가 많으니 문제 패턴에 익숙해지는 것도 좋다.