Greedy(탐욕) Algorithm?

Greedy Algorithm이 뭐야?

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

• 예를 들어 편의점 알바를 할때 손님이 4040원 어치의 물건을 사려고 하고 5000원을 주면서 거스름돈(동전)은 최소한으로 해서 거슬러 달라고 했다 치자.

• 그럴때 최소한의 동전으로 거슬러 주려면 우선 거스름돈 960원의 값에서 가장 큰 값의 동전인 500원을 하나 선택하고 생각을 해보는거다. 500원짜리 동전 하나를 더 선택할 순 없나? 만약 500원짜리 동전을 하나 더 선택하게 되면 거스름돈인 960원보다 금액이 커지기 때문에 적합하지 않다 라고 판단을 내리고 그 다음으로 넘어가 500원보다 그 다음으로 큰 동전인 100원짜리 동전을 4개 선택을 한다. 그리고 또 생각을 하는거다. 100원짜리 동전 하나를 더 선택할 순 없는지, 만약 100원짜리 동전을 하나 더 선택하게 된다면 금액이 또 거스름돈보다 커지기 때문에 적합하지 않다고 판단 내리고 다음으로 큰 동전으로 또 넘어가고 넘어가고 계속 그런식으로 해서 적절하게 금액에 맞게 최소한의 동전수로 거스름돈을 거슬러 주는것이다.

• 위와같은 방식으로 문제를 해결하게 된다면 비교적 빠른 시간내에 어느정도 합리적인 결과를 도출해낼 수 있지만 항상, 가장 최적의 결과를 도출하진 못하게 된다.

• 한가지 예를 더 들자면 내가 도둑이고 딱 35kg만 들어갈 수 있는 가방이 있다고 했을때, 내가 훔칠 수 있는 물건들이 아래와 같다고 해보자.

  ㄴ 그림작품 30kg, 3000 달러의 값어치.
  ㄴ 티비 25kg, 2500 달러의 값어치.
  ㄴ 컴퓨터 20kg, 2000 달러의 값어치.
  ㄴ 다이아 반지 15kg, 1500 달러의 값어치.

• 위와 같은 물건들이 있을때 Greedy Algorithm을 적용해서 물건을 훔치게 된다면 우선 가장 비싼 물건을 선택해 가방에 담아야 하는데, 가장 비싼 물건인 그림작품을 가방에 넣게 되면 35kg 중 30kg가 차기 때문에 다음 물건을 넣을 수 없게 되고 그렇게 되면 내가 훔치는 물건의 값은 3000 달러에 그치게 된다.

• 위와같은 방법이 최적의 방법이라고 할 수 없는게, 만약 컴퓨터 20kg와, 다이아반지 15kg을 훔치게 되면 총 35kg의 가방도 꽉 채울 수 있고 물건들의 값어치도 3500 달러가 되기때문에 가장 최적의 방법으로 물건을 훔지는게 가능하다.

• 때문에 Greedy Algorithm이 항상 최적의 결과를 도출해낼 수 없다고 하는것이다.