[알고리즘] Greedy(탐욕) 알고리즘

알고리즘은 두 종류의 알고리즘이 있다.

1. iterative algirithm : 계속해서 답을 고쳐나가는 알고리즘 => 느리나 정교함

2. constructive algorithm : 한번정한 것을 바꾸지 못함 => 빠름

 

 그리디 알고리즘은 전형적인 constructive alogirithm이다. 매 순간마다 최적의 방법을 선택하면서 진행된다. 따라서 그리디 알고리즘으로 문제를 해결해나가고자 한다면 한 순간에서는 최적의 값을 낼 수 있을지는 몰라도 전체적으로는 최적의 답을 찾지 못할 가능성이 적지 않다. 그렇다면 정확성이 떻어지는 greedy 알고리즘 기법은 어디에 사용할까?

1. greedy 알고리즘으로도 최적의 답을 도출해낼 수 있을 때

2. 다른 방법으로 짠 알고리즘의 비교 대상으로 사용할 수 있다.

 

 먼저, 그리디 알고리즘으로 해결하지 못하는 문제의 예시를 들어보겠다. 편의점에 가서 10000원에 딱 맞춰서 물건을 사고자 한다. 물건 가격은 초콜렛 1500원, 피자 6000원, 핫도그 2000원, 컵라면 1000원, 냉동막창 5500원이 있다고 하자. 그리디 알고리즘에 의하면 먼저 10000원에 가장 가까운 비싼 피자를 살 것이다. 그리고 남은 물건들 중 가장 비싸고 4000원보다 싼 핫도그를 사고 같은 방식으로 초콜렛을 살 것이다. 그렇다면 500원이 남게 된다. 그러나 초콜렛, 핫도그, 컵라면, 냉동막창을 사면 10000원에 딱 맞춰서 물건을 살 수 있다.

 이제 그리디 알고리즘으로 최적의 답을 도출해낼 수 있는 예시를 들어보겠다. 바로 가장 적은 수의 동전으로 잔돈을 거슬러 주는 것이다. 750원을 거슬러줘야 하는 상황이라고 가정하자. 먼저 750원보다 작은 가장 큰 금액인 500원을 거슬러주고 250원보다 작은 가장 큰 금액인 100원, 100원 50원보다 가장 작은 금액인 50원을 거슬러 줄 것이다. 이는 가장 최적의 답이 된다.

 위 단락의 case는 왜 그리디 알고리즘으로 해결할 수 있을까? 그 이유는 500원의 100의 배수, 100원은 50의 배수, 50원은 10원의 배수이기 때문이다.