[알고리즘] 욕심쟁이 방법

[알고리즘] 욕심쟁이 방법

 

-알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.

 

1. 욕심쟁이 방법(Greedy Algorithm)
-탐욕 알고리즘, 그리디 알고리즘이라고도 불린다.

-욕심쟁이 방법이란 일련의 선택 과정을 통해 해를 찾는데, 전후 단계의 선택과정과 관계 없이 각 단계마다 정해진기준에 따라 가장 최선이라고 여겨지는 국부적인 최적해를 찾아나가면 결과적으로 전체적인 최적해를 구할 수 있다는 전략을 취하는 방식이다.

-어떤 문제에 욕심쟁이 방법을 적용할 수 있다면, 최적해를 보장하는 효율적인 알고리즘을 가장 간단히 만들 수 있는 방식이다.

-가능한 여러 해 중 최솟값/최대값을 찾는 최적해 문제에 주로 사용된다.

-ex: 거스름돈 문제, 배당 문제와 같은 비교적 간단한 문제들

 

 

2. 거스름돈 문제

(1) 일반적인 경우

-거스름돈이 780원일 때, 고객에게 돌려줄 동전의 최소 개수를 구해보자. 이 때 사용가능한 동전의 갯수는 500/100/50/10원 총 네 종류가 있다.

-> 욕심쟁이 방법을 적용한다면, 액면가가 큰 동전부터 '욕심을 부려서' 최대한 뽑아 거스름돈을 만드는 것이다.

-> 500x1, 100x2, 50x1, 10x3 -> 총 7개의 동전을 거슬러 줄 수 있다.

 

(2) 120원의 동전이 존재할 때

-거스름돈이 650원일 때, 고객에게 돌려줄 동전의 최소 개수를 구해보자. 이 때 사용가능한 동전의 갯수는 500/120/100/50/10원 총 네 종류가 있다.

-> 욕심쟁이 방법을 적용한다면 500원 1개, 120원 1개, 10원 3개라는 결론이 나온다. 하지만 이는 최적해가 아니다.

-> 500원 1개, 100원 1개, 50원 1개를 사용하면 동전을 3개만 사용하고로 거스름돈을 줄 수 있다.

-> 이와 같이 거스름돈 문제라고 해도, 동전의 액면가가 일반적인 경우에는 욕심쟁이 방법을 사용할 수 없음!