탐욕 알고리즘

1. 대학교 수업시간표 짜기 문제

대학교에서 수강신청을 할 예정인데 최대한 많은 과목을 듣고 싶다.

하지만 시간이 한정적이고 시간이 겹치는 시간대에 동시에 두과목을 들을순 없다.

시간이 겹치지 않고 수강신청을 하되 가장 많이 과목을 들을수 있게 시간표를 짜고 싶다.

수강신청 가능 목록

과목명	시작 시간	종료 시간
자바	09:00	10:00
안드로이드	09:30	10:30
IOS	10:00	11:00
자료구조	10:30	11:30
알고리즘	11:00	12:00

시간이 일부 겹치기 때문에 이 수업들을 모두 듣지는 못한다.

하지만 되도록 많은 과목을 듣고싶다. 어떤과목을 신청해야 가장 많은 수업을 들을수 있을까?

1. 가장빨리 끝나는 과목을 고른다. 이 과목이 처음으로 신청해야할 과목이다.

2. 첫번쨰 과목이 끝난후에 시작하는 과목을 고르는데 마찬가지로 가장 빨리 끝나는 과목을 고른다. 

이 과목이 두번쨰로 신청해야 할 과목이다.

이런식으로 반복하면 정답을 얻을 수 있다.

자바가 오전 10시에 끝나니깐 가장 빨리 끝나는 과목이다. 자바를 먼저 신청해야 한다.

오전 10시 이후에 시작하고 가장 빨리 끝나는 수업을 다음으로 고릅니다. 안드로이드는 자바와 충돌하니까 안되고 IOS을 선택한다.

자료구조는 IOS와 충돌하니까 알고리즘을 고른다.

자바 IOS 알고리즘이 신청해야할 과목이다.

간단하다는 것 그것이 탐욕 알고리즘의 장점이다. 

각각의 단계에서 최적의 수를 찾아내면 된다.

과목 중에서 가장 빨리 끝나는 수업을 선택하는것이 목표이다.

국소최적해(locally optimal solution)을 찾음으로서

전역최적해(globally optimal solution)을 구하게 된다.

하지만 탐욕알고리즘이 항상 성공하는 것은 아니다.

2. 배낭채우기 문제

나는 탐욕스러운 도둑이다. 훔친 물건을 넣어 둘 배낭이 있는데 이 배낭은 35kg의 무게까지만 담을 수 있다.

배낭에 넣을 물건의 가격의 합을 최대한 크게 하고 싶다.

1. 가방에 들어갈 수 있는 것 중에서 가장 비싼물건을 고른다.

2. 가방에 들어갈수 있는 물건 중에 가장 비싼 것을 고른다. 

계속 반복한다.

하지만 이 알고리즘은 제대로 동작하지 않는다. 

예를 들어 내가 훔칠수 있는 물건이 3개가 있다.

무게	이름	가격
30kg	에어컨	30만원
20kg	냉풍기	20만원
15kg	자전거	15만원

배낭에는 35kg까지 들어간다. 에어컨이 30만원으로 가장 비싸니까 에어컨을 훔치면 다른것을 넣을 수 없다.

하지만 냉풍기와 자전거를 같이 훔치면 35kg이 되고 35만원이 된다.

분명히 탐욕 알고리즘은 올바른 답을 내놓지 못한다.

하지만 정답에 상당히 가까운 답이기도 하다.

3. 집합 커버링 문제

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

8개의 지역도시에 있는 모든사람에게 이 라디오 쇼를 들려주고 싶다.

하나의 방속국을 통해 청취할 수 있는 지역이 한정되어 있다.

전국에 흩어져 있는 대도시 라디오 방송국들을 방문해 라디오 쇼를 진행할 예정이다.

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

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

일단 방송국 목록은 다음과 같다.

대도시 방송국	지역 도시
서울 방송국	김포 천안 안동
인천 방송국	부천 김포 광명
세종 방송국	공주 천안 구미
대구 방송국	천안 안동
부산 방송국	구미 경주

각 방송국 마다 커버할수 있는 지역이 서로 다르고 겹치는 지역이 있을 수도 있다.

8개의 지역도시 전체를 커버하는 가장 적은 수의 방송국의 집합은 어떻게 구해야 할까? 

1. 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할수 있는 방송국을 고른다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 상관 없다.

2. 모든 도시에 방송이 될때까지 선택을 반복한다.

이것이 근사 알고리즘이다.

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

근사알고리즘의 성능은 

1. 얼마나 빠른가?

2. 최적해에 얼마나 가까운가?

두가지로 판단한다.

탐욕 알고리즘은 다루기 간단할 뿐더러 그 단순함으로 인해 실행속도가 빠르기 때문에 좋은 선택이 될수 있다.

1. 파이썬의 set과 집합 표현

fruits = set(["avocado","tomato","banana"])
vegetables = set(["beets","avocado","tomato"])
 
print(fruits | vegetables) # 합집합
# {'banana', 'beets', 'avocado', 'tomato'}
 
print(fruits & vegetables) # 교집합
# {'avocado', 'tomato'}
 
print(fruits - vegetables) # 차집합
# {'banana'}
 
# 집합은 리스트와 비슷하지만 중복을 허용하지 않는다.
 
arr = [1,2,2,3,3,3]
print(set(arr))
# 집합으로 변환 [1,2,2,3,3,3] 리스트 to (1,2,3) 집합
# {1, 2, 3}

2. 근사 알고리즘을 사용한 집합 커버링 방송국 방송하기 구현

# 방송이 필요한 도시
city_needed = set(["광명","부천","공주","김포","천안","안동","구미","경주"])
print(city_needed)
# {'광명', '부천', '공주', '김포', '천안', '안동', '구미', '경주'}
 
# 방송국은 주요대도시에 5군데 있고 주요대도시방송국은 지역도시의 방송을 커버한다.
stations = {}
stations["서울"] = set(["김포","천안","안동"])
stations["인천"] = set(["부천","김포","광명"])
stations["세종"] = set(["공주","천안","구미"])
stations["대구"] = set(["천안","안동"])
stations["부산"] = set(["구미","경주"])
 
print(stations)
'''
{
 '서울': {'김포', '천안', '안동'},
 '인천': {'부천', '김포', '광명'},
 '세종': {'공주', '천안', '구미'},
 '대구': {'천안', '안동'},
 '부산': {'구미', '경주'}
}
'''
 
final_stations = set()
 
# 모든 방송국을 하나씩 보면서 아직 방송이 되지 않는 도시 중에서
# 가장 많은 도시를 커버하고 있는 방송국을 고른다.
# 이 방송국을 best_station이라고 하겠다.
 
while city_needed:
    best_station = None
    city_covered = set() # city_covered는 아직 방송되지 않은 도시 중에서 해당 방송국이 커버하는 도시의 집합이다.
    for station, states_for_station in stations.items():
        covered = city_needed & states_for_station # {"광명","부천","공주","김포","천안","안동","구미","경주"} & {"김포","천안","안동"}
        if len(covered) > len(city_covered): # 이 방송국이 현재의 best_sation보다 더 많은 도시를 커버하는지 확인
            best_station = station # 커버한다면 이 방송국이 새로운 best_station
            city_covered = covered
            
    final_stations.add(best_station)
    city_needed -= city_covered # city_needed가 완전히 빌때까지 반복한다.
 
print(final_stations)
# {'인천', '세종', '서울', '부산'}

집합 커버링 문제를 풀기 위해서는 가능한 모든 집합을 계산해야 한다.

approximation1.py