Greedy Algorithm

Greedy Algorithm 탐욕 알고리즘

• 개념 :  최적해를 구하는 데에 사용되는 근사적인 방법. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
•  (미래를 생각하지 않고 각 단계에서 최선의 선택을 함)

• 그리디 알고리즘으로 최적의 해를 구할 수 있는 문제가 많지는 않다.
• 그리디 알고리즘이 사용되는 경우 ->   탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우 (DP보다 수행시간 훨씬 빠르므로 유용)

---

• 예시 문제 ① : 동전 개수

        10원, 50원, 100원, 500원짜리 동전들을 이용하여 어떤 금액을 표현하자. 

        이때 각 동전은 무수히 많은 대신 동전 개수를 최소로 사용해야 한다.

        풀이>> 무조건 사용할 수 있는 한 가장 큰 금액의 동전을 많이 사용하면 된다.

•     예시 문제 ② : 도시락 

        N개의 도시락이 있고, 전자레인지는 단 한 대만 존재하며 한 번에 하나의 도시락만 데울 수 있고, 각 도시락은 조리 시간과 먹는 시간이 다르게 정해져 있다. 이때 도시락을 적절한 순서로 조리하여 첫 번째 도시락을 데우기 시작한 순간부터 모든 도시락을 먹는 데 걸리는 시간이 최소가 되게 해야 한다. (다 데운 도시락은 바로 누군가가 먹는다.)

     

     풀이 >> 먹는 데 시간이 오래 걸리는 도시락부터 순서대로 데운다.

     이유 >> 도시락을 데우고 나서 바로 다른 도시락을 데우는 걸 반복하고, 각 도시락을 데우는 시간은 정해져 있으므로 우리는 도시락을 데우는 시간을 줄일 수 없다.

                 그러나 만약 마지막으로 데운 도시락을 먹는 데 오랜 시간이 걸린다면 전체 시간이 길어질 것이므로 오래 걸리는 것을 먼저 데우고 먼저 먹기 시작하는 것이 좋다.

•     예시 문제 ③ : 멀티탭 스케줄링

        멀티탭 구멍의 개수가 N개가 있다. 근데 전기 용품은 K개가 있고 전기 용품들의 사용 순서를 알고 있을때, 플래그를 빼는 횟수를 최소화 해야 한다. 

        풀이 >> 사용 순서를 알고 있으니 이미 꽂혀있는 전기 용품들 중 가장 나중에 사용하는 전기 용품을 뽑는다.