그림으로 개념을 이해하는 알고리즘

CH 08 탐욕 알고리즘

- 탐욕 알고리즘 : 각각의 단계에서 최적의 수 찾기 (=국소최적해)

> 최종적으로 전역 최적해를 산출

- 근사 알고리즘 : 정답과 가장 비슷한 값 유추 (정확한 답 계산에 시간이 너무 오래걸릴 경우)

> 성능 기준 : 얼마나 빠른지, 최적해에 얼마나 가까운지

- 집합 커버링 문제 : 가능한 모든 집합을 계산해야 풀이 가능

> 모든 경우의 수를 따져서 최단/최소를 구하는 문제 => NP-완전 문제

** NP-완전 문제 특징

1) 항목에 적을 때는 알고리즘이 빠른데, 항목이 늘어나면 갑자기 느려짐

2) 'X의 모든 조합'과 같은 표현

3) 더 작은 하위 문제로 변환할 수 없어 X의 가능한 모든 버전을 계산해야하는 경우

## CH 08. 탐욕 알고리즘

states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

stations = {}
stations["kone"] = set(["id", "nv", "ut"]) # 집합 형태로 저장
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])

final_stations = set()

while states_needed:
  best_station = None
  states_covered = set()
  for station, states in stations.items():
    covered = states_needed & states ## 교집합
    if len(covered) > len(states_covered):
      best_station = station
      states_covered = covered

  states_needed -= states_covered
  final_stations.add(best_station)

print(final_stations)