greedy algorithm

keywords

• find optimal in each step
• approximation

의의

완벽한 것보다 충분히 좋은 것을 찾는다.

Knapsack problem

---

#. 상황

• 가방을 가지고 있다.
• 가방에 넣을 도구들을 가지고 있다.

#. 목적, 조건

• 가방에 도구들을 담고 싶다.
• 가방의 공간을 최대한 남김없이 활용하고 싶다.

#. greedy approach

• 남아있는 도구들 중에서,
• 가장 부피가 작은 것을 넣는다.
• 반복 한다.

기지국 선택

---

#. 상황

• 방송을 기지국을 이용해서 송출하려고 한다.
• 각 기지국은 방송을 송출할 수 있는 도시를 리스트로 가지고 있다.
• 기지국별 리스트는 서로 겹친다.

#. 목적

• 최소한의 기지국을 이용해서 전지역을 커버하고 싶다.

#. greedy approach

• 남아있는 것 중 가장 많은 도시를 커버하는 기지국을 고른다.
• 방송을 송출해야할 도시의 리스트를 업데이트 한다.

#. pseudo algorithm step by step

bestStations = set();
while 남아있는_도시들:
    // 최적의 기지국 찾기
    bestStation = None;
    coveredCities = set();
    for station in stations:
    	covered = stationCover & 남아있는_도시들;
        if (len(covered) > len(coveredCities):
        	bestStation = station;
            coveredCities = covered;
    // 업데이트
    남아있는_도시들 -= coveredCities;
    bestStations.push(bestStation);