Greedy

1. 앞에 놓인 선택지들 중 바로 보이는 것을 딱! 고르면 그게 항상 최선이 될 수 있도록 문제의 구성요소를 변형 및 접근하여 해결하는 방법
   • 선택한것은 순간적으로는 최적해가 될 수 있지만, 그 선택들이 모여 전체적으로 최적해가 되는지는 보장할 수 없다.
     • 당장 눈앞에 보이는것만 근사적으로 접근했을때 최적이다. (보통 문제가 그렇게 주어진다. 따라서 입력 유형이 조금만 바뀌어도..)
   • 최적부분 구조(optimal substructure)를 만족시키는 구조를 먼저 완성시키고, 자연스럽게 선택지를 선택할 수 있도록 한다.
     • optimal substructure: 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있다는 개념
   • 앞의 선택이 이후의 선택에 영향을 주지 않아야 한다
2. DP처럼 작은 문제를 통해 큰 문제를 해결할 수 있는 구조처럼 생겼지만, 접근해야 할 작은 문제가 너무 많아서 시간복잡도가 과도하게 커지는 경우에 욕심쟁이 알고리즘을 의심할 수 있음
3. 가끔 정렬하거나 Min Heap or Max Heap(Priority Queue)자료구조를 쓰도록 유도되어있다.
4. 정렬하는 경우: 일반적으로 Exchange Argument(Swapping Argument) 테크닉으로 증명할 수 있음 N개의 원소를 특정 순서대로 배열해서 가장 좋은 배열 순서를 찾아야 하는 경우(BOJ 14908 구두 수선공): 인접한 두 원소를 교체했을 때 반드시 이득이면 그 기준을 바탕으로 정렬할 수 있음