그리디(greedy) 알고리즘

1. What?

: 그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만을 고르는 방법입니다.

  쉽게 말해서 어떤 문제를 풀때 가장 "간단하게" 푸는 방식입니다.

  따라서 코딩테스트에서의 그리디 알고리즘 문제를 풀때는

  상황을 "극단적으로" 몰고 가서 (상황을 단순화 해서)가장 간단한 해법을 도출하는 방식으로 풀어야 합니다.

2. When?

: 그리디 알고리즘은 문제에서 최댓값 또는 최솟값등 "극단적인"상황의 값(단순한 상황에서의 값)을 찾으라고 할 때 사용합니다.

 

3. How?

: 그리디 알고리즘 문제를 풀기 위해서는 최소한의 아이디어가 필요한데 대표적인 아이디어는 "올림차순,내림차순"입니다.

하나의 예시를 살펴보도록 하겠습니다.

 

<문제>(이코데의 그리디 알고리즘 문제에서..)

 

당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원,100원,50원,10원짜리 동전이 있습니다

손님에게 거슬러 주어야 할 돈이 N원 일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요

 

<해결>

문제에서 최소 개수 즉 극단적인 상황의 값을 찾으라고 했으므로 이 문제는 그리디 알고리즘 문제 입니다.

동전을 가장 적게 쓰기 위해서는 500원으로 거스름을 해주고 그 동전으로 해결할 수 없을때 100원 그 다음 50원

이렇게 처음에는 큰 동전으로 거슬러 주면서 점차 작은 동전으로 거슬러 주면 됩니다.(올림차순)

이처럼 그리디 알고리즘 문제를 푸는데 필요한 기본적인 아이디어로는 올림차순, 내림차순이 있다는 것을 확인할 수 있었습니다.

##### 주의 

그리디 알고리즘 문제에서는 그리디 알고리즘 말고 다른 방법으로 동전을 최소화 할 수 있는지 살펴 봐야 합니다

이 문제에서는 거스름돈이 다 10의 배수 이므로 그리디 알고리즘이 가장 타당한 문제 풀이 입니다.