그리디 알고리즘은 최적해를 구하는 데 사용되는 알고리즘 중 하나이다. 이 알고리즘은 매 순간마다 가장 최선의 선택을 하는 것으로, 매 순간의 최선의 선택들이 모여 전체적으로 최적의 해를 구하게 된다.
그리디는 기본적으로 아이디어 싸움이다. 아이디어를 빠르게 떠올리면 다이아문제여도 금방 해결 가능하고 아이디어가 떠오르지 않는다면 브론즈도 헬 난이도가 되는 것 같다.
그래도 그나마 그리디를 해결하는데 중요한것은
예를 들어, 동전 문제를 생각해보자. 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하자. 이 때, 가장 적은 동전을 사용해서 거슬러 주어야 하는 금액이 1260원이라면 어떻게 해야 할까? 가장 큰 단위인 500원부터 차례대로 거슬러 줄 수 있는 만큼 거슬러주면 최적의 해를 구할 수 있다. 따라서, 500원 2개, 100원 2개, 50원 1개, 10원 1개를 거슬러 주어야 하는 것이다.
이와 같이 그리디 알고리즘은 매 순간 최적이라고 생각되는 것을 선택하여 최종적인 해답에 도달한다.
예를 들어, 1원, 4원, 6원짜리 동전이 무한히 존재한다고 가정하자. 이 때, 가장 적은 동전을 사용해서 8원을 거슬러 주어야 할 때, 그리디 알고리즘을 사용하면 6원, 1원, 1원으로 총 3개의 동전을 거슬러줄 것이다. 하지만 최적해는 4원 2개로 총 2개의 동전으로 거슬러줄 수 있다. 이와 같이 그리디 알고리즘은 항상 최적의 해를 보장해주지 않는다는 것을 기억해야 한다.