［알고리즘 / Algorithm］ 당장 좋은 것만 선택하는 그리디

그리디 알고리즘은 단어 그대로 번역하여 탐욕 알고리즘으로도 소개된다. 탐욕적이라는 말이 무슨 뜻일까?

Greedy Algorithm

그리디 알고리즘에서의 탐욕적이다 라는 말은 현재 상황에서 당장 좋은 것만 고르는 방법을 의미한다. 그래서 어떻게 보면 무식하게 문제를 푸는 방법이라고 볼 수 있다. 단지 매 순간마다 가장 좋아보이는 것을 선택하고, 이 선택이 나중에 어떠한 영향을 미칠지에 대해서는 전혀 고려하지 않는다.
코딩 테스트에서 나오는 그리디 알고리즘 문제들은 타 알고리즘과 비교했을 때 미리 외우고 있지 않아도 풀 수 있을 가능성이 높다고 한다. 하지만 문제 유형이 굉장히 다양하기 때문에 많은 유형을 접하면서 연습을 하는 것이 중요하다.

선택을 위한 기준

매 순간 좋은 것을 선택하기 위해서는 기준이 있다. 이러한 기준은 문제에서 알게 모르게 제시해준다고 하는데, 가장 큰 순서대로, 가장 작은 순서대로 처럼 특정한 기준이 나온다면 그리디 알고리즘으로 쉽게 풀 수 있을 것이다. 그리디 알고리즘의 대표적인 유형인 거스름돈 문제를 살펴보자.

거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 
카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 
단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

풀이는 굉장히 간단하다. 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.

참고

• 이것이 취업을 위한 코딩 테스트다