[Algorithm] 그리디(greedy, 탐욕법)

그리디 알고리즘

• 그리디: 탐욕법. 어떤 문제가 있을 때 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’으로 문제 푸는 것. 현재의 선택이 나중에 미칠 영향은 고려 X
• 현재 상황에서 가장 좋아 보이는 것만을 선택해도 풀 수 있는 문제
• 보통 정렬 기준 제시해줌: 큰 순서대로, 작은 순서대로 등

그리디 알고리즘의 정당성

• 풀이를 위한 아이디어 떠올리고 이것이 정당한지 검토할 수 있어야
• 부분 문제로 나눠서 구한 답이 전체 문제의 일부
• 부분적인 최적 전략을 반복적으로 하면 답이 나오는 문제

---

참고

• 이것이 취업을 위한 코딩테스트다