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)
참고자료
Hello Coding 그림으로 개념을 이해하는 알고리즘
