알고리즘	풀이 가능한 문제들의 특징	풀이 가능한 문제 및 알고리즘
다이나믹 프로그래밍	최적 부분 구조(Optimal Substructure) 중복된 하위 문제들(Overlapping Subproblems)	0-1 배낭문제 피보나치 수열 다익스트라 알고리즘
그리디 알고리즘	최적 부분 구조(Optimal Substructure) 탐욕 선택 속성(Greedy Choice Property)	분할 가능 배낭 문제 다익스트라 알고리즘
분할 정복	최적 부분 구조(Optimal Substructure)	병합 정렬 퀵 정렬

그리디(Greedy) 알고리즘 이란?

Greedy란 탐욕스러운 이라는 뜻을 가진 단어이다.
이에 따른 Greedy Algorithm은 어떠한 문제가 있을 때 탐욕적으로 문제를 해결하는 알고리즘으로 탐욕 알고리즘, 탐욕법 등으로 불린다.

여기서 탐욕적이라는 말은 현재 상황에서 가장 좋은 것만 고르는 방법을 의미하며 매 순간 가장 좋아 보이는 것을 선택하고, 현제의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 탐욕적으로 선택해 최종적인 해답을 구한다.
순간마다 하는 선택은 그 순간에 대해 부분적(지역적)으로는 최적이지만, 그 선택들을 수집하여 만든 최종적(전역적)인 해답이 최적이라는 보장은 없다.
하지만 그리디 알고리즘을 적용할 수 있는 문제들은 부분적(지역적)으로 최적이면서 전역적으로 최적인 문제들이다.

✍️ 그리디 알고리즘의 최적해를 구하기 위한 조건

그리디(탐욕) 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.

탐욕스런 선택 조건(greedy choice property)은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며

최적 부분 구조 조건(optimal substructure)은 문제(전역적)에 대한 최적해가 부분 문제(지역적)에서도 최적해라는 것 이다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다.
하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.

✍️ 코딩테스트에서의 그리디 알고리즘

코딩테스트에서의 그리디 알고리즘 유형 문제는 정렬, 최단 경로 등의 유형과 다르게 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다.

여러 개의 데이터를 빠르게 정렬해야 하는 정렬 문제는 정렬 라이브러리의 사용법을 알고 있어야 하며, 최단 경로를 빠르게 찾는 최단 경로 문제는 플로이드 워셜(Floyd-Warshall) 혹은 다익스트라(Dijkstra) 같은 알고리즘을 알고 있거나 팀 노트를 준비해야 풀 수 있지만 (다익스트라(Dijkstra)는 그리디 알고리즘에 속하지,만 '암기'가 필요한 특이 케이스이다.)

보통 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구하기 때문에 사전 지식 없이도 풀 수 있기도 한 문제이다.

그러나 그리디 알고리즘 유형의 문제는 매우 다양하기에 많은 유형을 접해보고 문제를 풀어보며 훈련을 진행해야 한다.

✍️ 그리디 + 정렬

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.

대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

✍️ 예시)거스름돈

https://www.acmicpc.net/problem/5585

그리디 알고리즘을 이용하여 풀 수 있는 대표적인 문제로 가장 큰 화폐부터 돈을 거슬러주는 아이디어만 있으면 문제를 해결할 수 있다.

a = 1000 - int(input())
cnt = 0

b = [500, 100, 50, 10, 5, 1]

for c in b:
    cnt  += a//c
    a %= c

print(cnt)

대부분의 그리디 알고리즘 문제는 위 예시처럼 문제 풀이를 위한 최소한의 아이디어을 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

다른 그리디 관련 백준 문제들은 아래의 링크에서 확인 가능하다.

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

---

Reference)
이것이 코딩테스트다 with 파이썬
https://ko.wikipedia.org/wiki/탐욕_알고리즘