개념

• 현재 상황에서 지금 당장 좋은 것만 고고르는 방법

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없다.
• 정당석 분석이 중요 = 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.

예시

문제1

5 -> 7 -> 9 = 21

문제2

해답

정당성 분석

코드

![](https://velog.velcdn.com/images/youhyeoneee/post/2686a0dc-8b78-4f20-86c5-229032d0a876/image.png)

시간 복잡도 분석

이용하는 경우

1. 일반적으로 최대한 적은 , 최대한 많은 이라는 문구가 문제에 들어가는 경우가 많다. 최대/최소의 경우의 수를 구할것을 요구하는 문제들이다.

2. 그리디를 사용할 수 있는 조건이 주어진다. (주로 문제를 읽고 조건을 찾아야한다.)

3. 정렬을 한 뒤 그것을 이용해 푸는 문제가 많다. (위 동전문제의 경우에도 동전을 내림차순으로 정렬한 뒤 하나 하나 사용해 나가야 할 것이다.)

문제

https://www.acmicpc.net/problemset?sort=ac_desc&algo=33

💡 참고 포스팅

• (이코테 2021 강의 몰아보기) 2. 그리디 & 구현
• [C++ 알고리즘] 그리디(탐욕법,Greedy Algorithm)