탐욕 알고리즘

탐욕 알고리즘은 간단합니다, 각각의 단계에서 최적의 수를 찾아내면 됩니다.

집합 커버링 문제

라디오쇼를 시작했다고 가정했을때

미국 50개의 주에 있는 모든 사람에게 이 라디오 쇼를 들려주고 싶다

하나의 방송국을 톨해 청취할수 있는 지역이 한정되어 있기 때문에 전국에 흩어져 있는 몇개의 라디오 방송국들을 방문해서

라디오쇼를 진행할 예정이다, 전국의 모든사람들이 최소한 한번은 쇼를 들을수 있도록 하려면 어떤 방송국을 방문해야할지 계산해한다

또 방송국을 방문하여 한번 쇼를 하는데 돈이 들기 때문에 최대한 적은 수의 방송국을 돌아야 한다.

근사 알고리즘

1. 아직 방송하지 않은 지역중 가장 많은 지역에 방송할수 있는 방송국을 고릅니다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 상관없습니다.
2. 모든 주에 방송이 될떄까지 반복합니다.

이것을 근사 알고리즘 이라고 합니다, 정확한 답을 계산하는데 시간이 너무 많이 걸린다면 근사 알고리즘을 사용할수 있습니다

해당 알고리즘의 성능은 "얼마나 빠른가" , "최척해에 얼마나 가까운가"

탐욕 알고리즞ㅁ은 다루기 간단할뿐더러 단순함으로 인해 실행속도가 빠르기에 좋은 선택이 될수 있다
이 경우 탐욕 알고리즘의 실행속도는 O(n2)시간이다. 여기서 n 은 방송국의 수 이빈다.