그리디 알고리즘은 현재 상테에서 볼 수 있는 선택지 중에 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

<aside> 💡 그리디 알고리즘은 잘 따져보지 않으면 반례가 생길 수 있다. (최적의 해를 보장하지 않음)

</aside>

그리디 알고리즘의 핵심 이론

그리디 알고리즘은 다음과 같은 3단계를 반복하면서 문제를 해결한다.

[11047] 동전 개수의 최솟값 구하기

[1715] 카드 정렬하기

[1744] 수를 묶어서 최댓값 만들기

[1931] 회의실 배정하기

[1541] 최솟값을 만드는 괄호 배치 찾기