Greedy algorithm (탐욕 알고리즘)

// Greedy algorithm

---

   What is Greedy algorithm?   

  답을 하나씩 골라가는데, 미리 정해놓은 기준에 따라 매번 가장 좋아 보이는 답을 선택하는 것이다. 하지만 <Greedy algorithm>을 이용하여 설계를 한다면 항상 최적의 해는 보장할 수 없다.

---

   Example   

  <Greedy algorithm>의 예시로 가장 많이 보여지는 것들 중 하나인 "거스름돈 문제"를 예시로 들어보자.

   "거스름돈 문제"란, 임의의 액수만큼 거스름돈을 주어야 하는데 최소한의 개수의 동전을 사용하여 주어야 할 때 해당되는 동전들을 고르는 문제이다. 예를 들어 만약 거스름돈으로 520원을 주어야 한다. 이때 520원을 줄 수 있는 방법은 다양하다. 하지만 상식적으로 10원짜리 동전 52개로 거슬러주는 것보단 500원짜리 동전 1개와 10원짜리 동전 2개로 거슬러주는게 맞다고 생각이 들 것이다. 520원을 거슬러주는 방법들중 10원짜리 동전 52개로 거슬러주는 것이 최악의 해이고 500원짜리 동전 1개와 10원짜리 동전 2개로 거슬러주는 것이 최적의 해임이 느껴질 것이다.

 

  이를 <Greedy algorithm>을 사용하여 구해보자. 주어진 조건은 가장 최소한의 동전을 가지고 거슬러주는 것으로, 이 문제에서 매번 가장 좋아보이는 답을 선택하기 위해선 가격을 넘지않는 선에서 집을 수 있는 가장 큰 가격의 동전을 골라야한다. 아래 표를 참고해보자.

 

	1st	2nd	3rd	4th	5th
500원	1개	1개	1개	1개	1개
100원		1개	100원짜리 내려놓음
50원			1개	50원짜리 내려놓음
10원				1개	2개
합계	500원	600원	550원	510원	520원

  <Greedy algorithm>이 항상 최적의 해를 보장하는것은 아니지만 지금 가정한 상황에선 가장 최적의 해를 구할 수 있게 되었다. 이렇게 문제를 풀면서 사용된 <Greedy algorithm>의 알고리즘 절차는 아래와 같다.

 

while (거슬러주어야 하는 돈보다 아직 부족하다면) {     집을 수 있는 가장 최적의 조건의 동전을 집는다; // 선택 과정       if (동전을 집었더니 거슬러주어야 하는 돈보다 액수가 많아졌다면) { // 적절성 검사        동전을 다시 내려놓는다;         continue;     }     else 거스름돈에 동전을 포함시킨다;       if (집은 거스름돈의 총액이 거슬러주어야 하는 돈과 같아졌다면) // 해답 점검        문제 해결;  }

  하지만 아까 설명하였듯, <Greedy algorithm>이 최적의 해를 나오지 못하게 하는 경우도 있다. 만약에 120원짜리 동전이 있다고 가정해보고, 160원을 거슬러주는 상황을 표로 표현해보자.

 

	1st	2nd	3rd	4th	... 7th
120원	1개	1개	1개	1개	1개
100원		1개	100원짜리 내려놓음
50원			1개	50원짜리 내려놓음
10원				1개	... 4개
합계	120원	220원	170원	130원	160원

  <Greedy algorithm>을 이용하여 주어진 상황을 해결하였더니 120원짜리 동전 1개와 10원짜리 동전 4개, 총 5개의 동전을 거슬러주어야 하는것을 볼 수 있다. 하지만 160원을 거슬러주는 최적의 해는 100원짜리 동전 1개, 50원짜리 동전 1개, 10원짜리 동전 1개이다. 따라서 위에서 <Greedy algorithm>을 사용하여 구한 해는 최적의 해가 아니다.

 

  <Greedy algorithm>을 사용하여 "거스름돈 문제"의 최적의 해를 찾으려면 동전들의 가치가 서로 배수, 약수 관계여야 하는 것 같다. (반례가 있다면 말씀해주세요!!)

 

  결론적으론, <Greedy algorithm>을 활용하여 문제를 해결하였을때 최적의 해를 찾았을수도 있지만 항상 최적의 해가 보장되는 것은 아니기에 <Greedy algorithm>으로 설계를 했다면, 최적의 해를 찾아주는지 항상 점검해야 한다.