그리디 알고리즘
당장 좋은 것만 선택
그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.
현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서
‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다.
대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그디리 알고리즘 문제는 정렬 알고리즘과 자주 짝을 이뤄 출제된다.
대표 문제: 거스름돈
카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
이 문제는 대표적인 그리디 문제다.
가장 큰 화폐단위 부터 돈을 거슬러주면 된다.
그리디 알고리즘의 정당성
대부분의 문제는 그리디 알고리즘을 이용했을 때 ‘최적의 해’를 찾을 수 없을 가능성이 높다.
하지만 위 거스름돈 문제는 탐욕적으로 접근했을 때 매우 효과적이다.
그 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
대부분의 그리디 알고리즘 문제에서 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
바로 문제 유형을 파악하기 어렵다면 다음과 같은 순서로 생각해보자.
1. 그리디 알고리즘을 먼저 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해본다.
2. 오랜 시간 고민해도 그리디로 해결할 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘으로 해결할 수 있는지 고민해본다.