그리디란 당장 좋은 것만 선택하는 알고리즘으로, 탐욕법이라고도 불린다.
이름에서 알 수 있듯 어떤 문제가 있을 때, 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘으로, 미래는 생각 안하고 현재 상황에서 가장 좋아 보이는 방향으로 문제를 풀어나가는 알고리즘이다.
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시한다.
가장 대표적인 문제로는 거스름돈 문제가 있다.
800원이 있을 때, 동전의 갯수를 최소한으로 주고 싶다.
이 문제는 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.
가장 먼저 500원을 거슬러 줄 수 있을 만큼 주고,
그 다음 100원, 50원, 10원을 거슬러 주면 최소 개수의 동전으로 줄 수 있다.
그리디 알고리즘의 정당성
당연히 그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다.
대부분의 문제는 그리디 알고리즘을 이용했을 때, '최적의 해'를 찾을 수 없을 가능성이 다분하다.
따라서 그리디 알고리즘으로 문제의 답을 찾았을 때는 그 답이 정당한지 검토할 필요성이 있다.
예를 들어 위에서 제시한 문제처럼 800원을 거슬러 준다면 500원 1개, 100원 3개로 답이 4개라고 나오는데, 최적의 해는 400원 2개이다.
다시 말해, 이 문제는 특이하게 큰 단위가 작은 단위의 배수 형태이므로 그리디 알고리즘으로 풀 수 있었던 것이다.
