Greedy Algorithm

• 모든 선택지를 고려하지 않고, 각 단계마다 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.
• 가장 직관적인 알고리즘 설계 패러다임이다.

그리디 알고리즘의 정당성 증명

• 탐욕적 선택 속성(greedy choice property)
  : 각 단계에서 탐욕적으로 내리는 선택이 항상 최적해로 가는 길 중 하나이다.
• 최적 부분 구조(optimal substructure)
  : 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있다.
  각 단계마다 어떻게 선택할 것인지 정해주어야 한다.

코딩테스트에서의 그리디

• 사전 지식 없이도 풀 수 있는 문제도 많지만, 많은 유형을 접해보고 문제를 풀어보면서 훈련을 해야한다.
• 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 것이기 때문에 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다고 한다.
  따라서 정렬 알고리즘과 짝을 이뤄서 출제되는 경우가 자주 있다.

참고

책 이것이 코딩 테스트다 with 파이썬
2021 ICPC 신촌 겨울 알고리즘 캠프 greedy 강의록