그리디 (Greedy) (1) - 그리디 알고리즘이란? / 예제 3.1) 거스름돈

그리디 알고리즘은 말 그대로 탐욕적인 알고리즘이라는 뜻을 내포한다. 그리디 알고리즘에서는 현재 상황에서 최적의 방법을 선택한다. 매 순간 가장 좋아보이는 방법을 선택하며 추후에 미칠 영향은 생각하지 않는 것이다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 사전에 암기하고 있지 않아도 풀 수 있는 가능성이 높은 유형이다. 그리디 알고리즘의 출제 유형은 매우 폭넓으므로 특이 케이스를 제외하고는 단순 암기를 통한 문제 해결은 힘들다. 이 유형은 '창의력'을 요구한다. 문제가 단순히 현재 상황에서 최적의 선택만을 해서 해결 가능한 문제인지를 파악할 수 있어야 한다.

코딩 테스트에서 그리디 알고리즘의 문제는 '가장 큰 (작은) 순서대로' 등과 같은 조건을 은밀히 제시한다. 따라서 그리디 알고리즘은 대체로 정렬 알고리즘과 짝을 이루는 경우가 많다. 

그러나 대부분의 문제에서는 그리디 알고리즘, 즉 현재 상황만 고려한 최적의 선택을 행하는 알고리즘을 구현했을 때 '최적의 해'를 찾을 가능성이 현저히 낮다. 반대로 그리디 알고리즘을 구현했을 때 해결가능하다는 정당한 보장을 떠올리면 해당 알고리즘은 매우 효과적이고 직관적이다. 즉 문제를 읽었을 때, 바로 문제의 유형을 파악하기 어렵다면 먼저 그리디 알고리즘을 의심하고 문제를 해결할 수 있는 '탐욕적'인 해결법이 존재하는지 검토하는 것도 좋은 방법이 될 수 있다.

결론적으로 그리디 알고리즘 문제는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당성을 검토해야 답을 도출할 수 있다.

그리디 알고리즘의 대표적인 예시인 '거스름돈' 문제를 살펴보자.

예제 3-1. 거스름돈
카운터에는 거스름돈으로 사용될 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한다고 할 때, 손님에게 거스름돈 N원을 거슬러 줘야 한다. 이 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, N은 항상 10의 배수이다.

이 예제에서의 핵심 키워드는 '동전의 최소 개수' 라고 생각한다. 동전의 개수가 최소가 되기 위해서는 가장 큰 화폐 단위인 500원을 최대로 선택하고 다음으로는 100원, 50원, 10원 순서대로 각각 최대 개수만큼 선택해야 한다. 따라서 이 문제는 그리디 알고리즘이 사용될 수 있는 것이다. 

예제 3-1 소스코드

거슬러 줘야 할 돈 N을 3780원이라고 가정한다. 순차적으로 가장 큰 화폐 단위인 500원, 100원, 50원, 10원 순서대로 거슬러 줄 수 있는 최대 개수로 거슬러 주면 최종적으로 거슬러 줄 동전 개수가 최소가 되는 것이다.

실행결과

실행결과 동전의 개수는 13개로 출력되는데, 500원 7개, 100원 2개, 50원 1개, 10원 3개로 이는 정답에 해당하는 것을 알 수 있다.