Persistence

집합 커버링 문제(set-covering problem) 근사 알고리즘 미국 50개 주에 방송을 하고 싶다. 이를 위해서는 방송국을 찾아가야 하는데, 이 방송국들은 각각 커버하는 주가 다르다. 방송국에 찾아가는 데는 비용이 드므로 방송국을 가장 적게 찾아가면서도 50개 주를 다 포함하게끔 하고 싶다. 이를 해결하기 위해 탐욕 알고리즘을 사용한다. (거의 정답에 가까운 답을 유추) 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할 수 있는 방송국을 고른다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 관계 없다. 모든 주에 방송이 될 때까지 반복한다. states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 방송하고자 하는 주의..