그리디
그리디란 당장 좋은 것만 선택하는 알고리즘으로 강력한 문제 해결 방법이다.
그리디는 국내에서 단어 그대로 번역하여 '탐욕법'으로 소개되는데 이름에서
알 수 있듯이 어떠한 문제가 있을 때, 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 쉽게 말해 미래는 생각 안하고 현재 상황에서 가장 좋아 보이는 방향으로 문제를 풀어나가는 알고리즘이다.
특징
만약 문제를 봤을 때, 처음 본 문제인데 왠지 풀 수 있을 것 같다면
그리디 문제일 확률이 높다.
그리디의 장점으로는 다른 알고리즘과 비교했을 때, 사전 지식 필요 없이 직관적으로 풀 수 있다는 장점이 있다.
사전 지식이 필요 없다는 것은 dfs나 bfs처럼 정해진 틀이 없고, 문제마다 코드가 너무 다르기 때문에 나온 말이다.
그렇기 때문에 그리디는 문제 출제의 폭이 매우 넓어, 특이 케이스를 제외하고는
정해진 풀이가 없어 모든 문제를 대처하기 어려운 점도 있다.
가장 중요한 것은 특정한 문제를 만났을 때, 단순히 현재 상황에서 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악하는 것이다.
거스름돈
그리디의 예시로 거스름돈 문제를 살펴보자.
1260원이 있을 때, 동전의 갯수를 최소한으로 하여 돈을 주고 싶다.
이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 아이디어만 떠올리면 쉽게 풀 수 있다.
바로 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.
가장 먼저 500원을 거슬러 줄 수 있을 만큼 준다.
그 다음 100원, 그 다음 50원, 그 다음 10원을 거슬러 주면 최소 개수의 동전으로 돈을 줄 수 있다.
정당성
그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는것은 당연히 아니다.
대부분의 문제는 그리디 알고리즘을 이용했을 때, '최적의 해'를 찾을 수 없을 가능성이 다분하다.
그리디 알고리즘으로 문제의 답을 찾았을 때는 그 답이 정당한지 검토해야 한다.
거스름돈 문제를 그리디 알고리즘을 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
예를 들어 800원을 거슬러 줘야 하는데, 화폐 단위가 500원, 400원, 100원이라고 해보자.
이 경우에 그리디 알고리즘으로는 500원 1개, 100원 3개로 답이 4개라고 나오는데, 최적의 해는 400원 2개이다.
다시 말해, 이 문제는 특이하게 큰 단위가 작은 단위의 배수 형태이므로 그리디 알고리즘으로 풀 수 있던 것이다.
대부분의 그리디 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.
어떤 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해보고, 문제를 해결할 수 있는 탐욕적인 해결법이 있는지 찾아보자.
만약 고민해도 그리디 알고리즘으로 해결할 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘 등 다른 알고리즘을 생각해보면 된다.
