<algorithm> 그리디 알고리즘

그리디 알고리즘은 개념은 굉장히 단순하다. 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다.

• 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

예제)

500원, 100원, 10원 동전이 무수히 많다고 가정할 때 가장 적은 수의 동전을 이용해서 1410원을 만든다고 하자. 이때 사용하는 동전의 개수는 몇개인가? 

 

이 문제를 접했다면 일반적으로 최대 500원의 개수를 사용할 것이다. 그래서 500원짜리 2개로 1000원을 만들고, 100원짜리 4개로 400원을, 10원 동전 1개로 10원을 만들어 1410원을 완성할 것이다. 따라서 이 문제의 답은 7개이다.

이 문제에는 그리디 알고리즘이 사용되었다. 쓸 수 있는 동전 중 가장 액수가 큰 것부터 순서대로 사용해 나간 것. 이 행동을 반복하면 문제를 풀어낼 수 있다.

 

이 문제를 위와 같이 단순한 방법으로 풀어낼 수 있는 이유는 작은 액수 동전이 큰 액수 동전의 약수이기 때문이다. 즉, 100원 5개로 만들수 있는 액수는 500원 동전 한개로 만들 수 있다. 그렇기 때문에 큰 액수의 동전부터 사용해 나가면 가장 적은 동전을 사용한다고 보장할 수 있는 것이다.

 

 

정리를 해보자면 그리디 알고리즘은 특정 상황에서만 사용할 수 있다. 즉 그리디를 사용한 방법이 정답이라는 보장이 되어야 사용할 수 있다.

 

모두 그런것은 아니지만 그리디 문제는 일반적으로 최대한 적은, 최대한 많은 이라는 문구가 문제에 들어가는 경우가 많다. 최대/최소의 경우의 수를 구할것을 요구하는 문제들이다. 그리고 그리디를 사용할 수 있는 조건이 주어진다. 

 

 

출처)

https://sectumsempra.tistory.com/88

[C++ 알고리즘] 그리디(탐욕법,Greedy Algorithm)