코딩테스트 공부하는 절차에 대해서 어느정도 서치해보셨다면, 보통은 기본적인 구현 문제들을 풀이한 뒤에는 그리디 알고리즘 문제부터 풀이해라! 라는 말들을 많이 접해보셨을 것 같습니다.
근데.. 그리디 알고리즘이 뭘까? 왜 탐욕이라는 표현을 왜 쓰는걸까요??

🤡 욕망의 항아리, 그리디 알고리즘

15,000원의 가격을 자랑하는 욕망의 항아리 카드..

이미지 출처 : http://www.11st.co.kr/products/2061799723

🍯 않이 그래서 욕망의 항아리 알고리즘이 뭔데?

욕망의 꿀단지🍯!!!!

그리디 알고리즘란, 매 순간 현재 기준으로 최선의 답을 선택해나가는 기법입니다.

즉, 매 순간 탐욕을 발휘해서 제일 좋은것 해를 취하는 것을 탐욕 이라고 표현하는거죠.

그러고보면 저도 매일 점심시간 어떤 메뉴를 먹어야 가장 최적의 행복을 도출할 수 있을지 고민하는 탐욕의 시간을 갖곤 합니다,,,

🍯 그래서 그리디 알고리즘에 뭐가 좋은데? 외 쓶은데?

그리디 알고리즘을 이용하면 빠르게 최적해로 가는 근사치를 구할 수 있습니다. 즉 제가 어떤 메뉴를 먹으면 최적으로 행복해질 수 있는지를 빠르게 파악할 수 있는거죠.

현재 상태에서 그걸 판별하는 것이기 때문에, 결과적으로 이건 최적해가 아닐수도 있습니다.
그저 빠르기 때문에 쓰는거고, 특정 조건에 해당하는 경우에만 적용이 가능합니다.

언제냐구요? 그건 아래에 설명 ~ ㅎ

🍯그리디 알고리즘에는 어떤 것들이 있을까

Activity Selection Problem

 N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 
 한 사람이 최대한 많이 할 수 있는 활동의 수 구하는 방법

출처 : https://www.webtoonguide.com/ko/board/totalreview/8380

• e.g. 응애 새내기인 제가 수강신청을 하는데, 시간표를 어떻게 짜야 최대한 많은 강의를 들을 수 있을까요? (새내기 아님, 대학 졸업한지 꽤 됨)

아래 수업 시간표를 봅시다.

class	A	B	C	D	E
시작	1	4	2	4	6
종료	5	5	3	7	10

각 수업에 대한 시작 시간과 종료 시간이 적혀있습니다. 일단 좀 뒤죽박죽이라 보기가 힘드네요.
종료시간을 기준으로 오름차순 정렬을 해보겠습니다.

class	C	A	B	D	E
시작	2	1	4	4	6
종료	3	5	5	7	10

헤르미온느가 되고싶은 새내기 랸나는 가장 많은 수업을 듣기 위해서는 먼저 어떤 수업을 들을까 고민합니다.

1. 현재 상황에서 가장 최적의 해인, 3시에 종료되는 수업인 C를 선택합니다.
2. 그리고 C 수업이 끝난 뒤에 생각해봤을때 가장 빨리 끝나는 수업을 생각해보면 A와 B중에 선택해야합니다.
3. 그런데 A는 1시에 시작하니 C와 겹쳐 들을 수 없네요. 어쩔수 없이 B를 선택합니다.
4. B 수업을 들은 뒤, 그 순간에서 선택할 수 있는 가장 빨리 끝나는 최적의 수업은 D이지만.. B와 시작 시작이 겹쳐서 고를 수 없습니다.
5. 자연스럽게 E 수업을 선택하게 되겠죠.

즉, 매 순간 최적의 해를 찾고 그것을 선택하게 되는 탐욕적인 판단법이죠!

그런데,, 몇번 이야기 했듯이 그리디 알고리즘은 매 순간 빠르게 판단할 수 있다는 장점은 있지만, 늘 이게 최적해를 보장해주진 못해요!

마시멜로 이야기를 떠올려보죠. 실은 15분을 기다리면 총 2개의 마시멜로를 먹을수 있지만, 그리디 알고리즘에 따르면 당장 1개를 먹는것이 가장 최적의 해가 됩니다. 즉 현재의 판단이 꼭 나중의 최적해를 보장해주는 것은 아니에요.

그래서 근사치를 구해도 되는 상황, 혹은 딥러닝 분야에서 근사치를 계속해서 구해나갈때 사용합니다.

🧑‍ 에엥..? 정확한 정답이 아니라 근사치를 구해요?

🧑‍: 에엥??? 그러면 코딩테스트에서 근사치를 구해도 되는거에용?;;
🕵️‍: 음.. 보통 코테는 근사치 구하는건 많진 않죠.. 코딩테스트 관점에서 본다면 아래 두 조건에 해당할때 그리디 알고리즘을 쓰면 좋다! 라고 이야기 할 수 있어요.

👨‍🏫 그리디 알고리즘을 사용하기 위한 특정 조건 (코딩테스트 관점)

1. 탐욕적 선택 특성 (Greedy choice property)

• 지금 선택이 다음 선택에 영향을 주지 않을 때 그리디 알고리즘을 사용할 수 있습니다.
  => 말만 보고는 잘 모르겠죠?

유튜브에서 보고 기가막히다고 생각한 예시를 들어보겠습니다. [개발자로 취업하기] 채널 정말 유용합니다.. 추천추천.. 감사합니다!

사진 및 내용 출처 : https://www.youtube.com/watch?v=_IZuE7NIeW4
(그리디 탐욕 Greedy 알고리즘 설명 7분만에 이해하기 / 개발자로 취업하기 채널)

1. 랸나는 서울에서 대전을 거쳐 부산을 간다고 할 때, 가장 짧게 갈 수 있는 경로를 구해야합니다.
2. 이때 서울에서 대전으로 가는 루트를 고른다고 해서, 대전에서 부산으로 가는 루트의 결정에 영향이 갈까요?
   => 아니죠! 서울에서 대전으로 가는 루트는 그냥 그 상황에서 최선의 루트를 고르는거고, 대전에서 부산으로 향하는 루트에 영향을 전혀 미치지 않죠.

이것을 바로 탐욕적 선택 특성 이라고 합니다.

2. 최적 부분 구조 (Optimal substructure)

• 전체 문제의 최적해는 부분 문제의 최적해로 이루어질 때
  => 이게 뭔말이냐구요? 같은 예시를 볼게요.
  
  사진 및 내용 출처 : https://www.youtube.com/watch?v=_IZuE7NIeW4
  (그리디 탐욕 Greedy 알고리즘 설명 7분만에 이해하기 / 개발자로 취업하기 채널)

1. 결국 서울에서 부산으로 향할때 가장 짧은 거리로 가는 길을 구하는 문제죠.
2. 그렇다면 서울에서 부산으로 향하는 루트는, 서울 & 대전, 대전 & 부산 각각의 최적의 루트의 합이 전체 경로의 최적해가 되는 것이죠!

그리디 알고리즘 풀이 전략

그렇다면 그리디 전략으로 문제를 풀겠다고 결정했을때, 문제를 어떻게 풀어나가야 할까요?

핵심은 정렬 입니다!

1. 어떻게 정렬을 해서 위의 두가지 조건을 만족할지 고민해야합니다.
   => 즉, 어떻게 정렬을 해야 미래의 조건은 따져보지 않고 현재만 고려해도 최적해를 구할 수 있을지 따져봐야 합니다.

---

아까 새내기 랸나의 수업 선택 상황으로 가봅시다.

class	A	B	C	D	E
시작	1	4	2	4	6
종료	5	5	3	7	10

헤르미온느 랸나가 가장 많은 수업을 들으려고 하면, 사실 수업이 언제 시작하는지, 얼마나 진행되는지는 고려할 필요가 없습니다.

그저 언제 끝나는지를 판단하여 가장 빨리 끝나는 수업을 찾아야겠죠.
=> 그래서 종료시간을 기준으로 오름차순 으로 정렬을 한 뒤 판단했던겁니다.
종료의 시간만 잘 정렬하면, 현재의 선택이 최적의 선택인것을 보장할 수 있는것이죠.

😮아니 그래서.. 다시 한 번 그리디 왜쓰냐구요?

그리디 알고리즘을 쓰는 이유는 정말 빠르기 때문입니다.
동적 계획법 (DP알고리즘) 도 유사하게 빠른 시간동안 최적해를 찾기 위한 알고리즘인데, 이 또한 다양한 전제조건이 있기 때문에 빠른 해를 구하려고 하다가도 조건에 부딪혀 속도가 느려지곤 합니다.

따라서 근사치를 구하더라도 빠르게 구하는 것이 목적일 때 그리디 알고리즘을 사용합니다.

예를 들어 네비게이션을 통해 서울까지 부산으로 가는 가장 빠른 길을 찾으려고 할 때, 만약 전국에 있는 모든 길을 전체 탐색하여 결과를 내놓는다면, 밤에 네비게이션을 켜놓고 아침에 일어나야 최적의 길 하나를 찾을 수 있겠죠.

길 안내는 차이가 크지 않다면, 빠르게 경로를 얻어내고 바로 길을 찾아주는게 좋겠죠.

---

그리디 알고리즘 문제 풀이

아래는 백준에서 그리디 알고리즘 문제들을 모아놓은 페이지입니다.
그리디 알고리즘은 정말 광범위하기도하고, 유형을 파악하기도 어렵다고 합니다!
그저 문제를 많이 풀어보고 적용해보는게 그리디 알고리즘을 파악하는데 큰 도움이 된다고 하니, 다들 많이 풀어보시고 익숙해져봅시다 :)
https://www.acmicpc.net/workbook/view/4380