[알고리즘] 탐욕 알고리즘 Greedy algorithm

1. 그리디 알고리즘이란?

 매순간 최적이라고 생각하는 경우를 선택하는 알고리즘입니다. 'greedy' 혹은 탐욕 이라고 이름이 붙은 이유는 전체적인 맥락에서의 최적과 각 순간(locally)에서 최적이라고 생각되는 경우가 다를 수도 있기 때문입니다. 그리디 알고리즘에서는 지나간 선택 중에서 혹시 더 좋은 경우의 수가 있었는지 돌아보지 않는다는 점이 동적 프로그래밍과 다른 점입니다.

2. 한계

'각 단계'에서의 최선을 선택하기 때문에 반드시 최적의 해를 구할 수 있는 것은 아닙니다.  따라서 overall optimal option 보다는 최적에 가장 가까운 값을 구하기 위해 사용하는 알고리즘입니다.

 최적의 답을 구해주지 않는다면 왜 그리디 알고리즘을 활용할까요? 그 이유는 시간 절약 때문입니다. 더 적은 시간을 들여 정답에 가까운 값을 구하고자 할 때 활용할 수 있겠습니다. 

3. Greedy vs Divide and Conquer vs Dynamic programming

Greedy	Divide & Conquer	Dynamic Programming
각 순간에서의 최선의 선택지를 고름으로써 최적화	더 간단한 문제의 서브문제로 나눔으로써 문제를 풀기 위해 multi-threading & recursion 을 활용	Divide and Conquer와 같지만 계산을 반복하지 않기 위해 서브문제의 각 답을 caching
항상 최적의 해를 찾지는 않지만, 매우 빠름	항상 최적의 해를 찾을 수 있지만 그리디보다 시간이 오래 걸림	항상 최적의 해를 찾을 수 있지만 적은 데이터셋에서는 소용 없음
메모리를 거의 사용하지 않음	재귀 호출을 기억하기 위해 메모리 사용	기억 및 테이블화에 많은 메모리 사용

참고: https://skerritt.blog/greedy-algorithms/

4. 문제풀이

백준 1931번, 11399번 on Github
extra problems: 백준 그리디 알고리즘 단계, 프로그래머스 그리디