[ Algorithm ] 탐욕 알고리즘

탐욕알고리즘 (Greedy Algorithm)

현재 상황에서 가장 좋아보이는 상황만을 선택하는 알고리즘이다.

흔히 그리디, 탐욕알고리즘이라고 부리기도 하며 최적의 해를 구하기위한

방법으로 사용될 때가 많다.

 

탐욕 알고리즘의 접근방법

1. 현재 상황에서 어떤 것을 선택할지 방법을 고안한다.

2. 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 정당성을 확인해야한다.

 

탐욕 알고리즘 문제

전형적인 탐욕 알고리즘을 이용해 풀 수 있느 문제로 "거스름 돈" 문제가 있다.

거스름 돈 문제를 통해서 그리디알고리즘에 대해서 이해해보자.

문제는 아래와 같은 조건과 답을 내어야 한다.

• 카운터에 500원 100원 50원 10원이 무수히 많다고 가정한다.
• 손님에게 11,480원을 거슬러 주어야 할때, 동전 개수의 최소값은?

결론부터 말하자면 이 문제의 해결방법은 가장 큰 화폐단위부터 거슬러 주는 것이다.

즉 500원부터 10원까지 거슬러 줄 수 있는 만큼 거술러주면 되는 것이다.

화폐단위	500원	100원	50원	10원
현재 금액	11,480	480	80	30
남은 금액	480	80	30	0
동전 개수	22	22 + 4	22 + 4 + 1	22 + 4 + 1 + 3

동전 개수의 최소값은 30이다.

 

큰 화폐부터동전의 개수를 구하며 내려왔을때 최적의 해를 구할 수 있는 이유는

각 화폐단위가 배수 관계에 속하기 때문에 그렇다.

 

예를 들어 640원을 거슬러 주어야한다고 하고 220원, 200원, 10원 동전이 있다고 가정하면

220원 2개, 200원 1개로 총 3개가 필요할 것이다. 이 또한 배수관계에 속하기 때문에

가장 큰 수의 동전부터 나눌 수 있는 만큼 나누고 점차 작은 수의 동전으로 나누어주는

같은 방식의 탐욕알고리즘을 사용하여 문제를 해결할 수 있다.

 

마치며...

탐욕알고리즘에 대해서는 간단하게 포스팅을 해보았다. 실질적으로 탐욕알고리즘은 코딩테스트를 볼 때 중요했던 개념이었다. 나는 탐욕알고리즘을 파악할때 예시로 주어지는 입력값과 출력값(정답)을 보며 연관성을 최대한 찾아보고 답을 만들기 위한 코드설계와의 연관성과 규칙성이 있는지를 확인하면서 코드를 작성할때 어떠한 연관성이 있는지를 파악하면서 실마리를 찾아냈던 것 같다. 개인적으로 익숙해지기 어려운 접근방식이었던 기억이 있다...