[Hello Coding 알고리즘] 8. 탐욕 알고리즘 greedy algorithm

Bibi·2021년 7월 5일

algorithm algorithm이론

Hello Coding 알고리즘

목록 보기

8/11

Hello Coding 알고리즘

8. 탐욕 알고리즘 greedy algorithm

수업 시간표 짜기 문제

탐욕 알고리즘을 적용하는 대표적인 문제.

가장 빨리 끝나는 과목을 고른다.
1에서 고른 과목이 끝난 후 시작하는 과목 중 가장 빨리 끝나는 과목을 고른다.
시간표가 꽉 찰 때까지 1,2를 반복한다.

탐욕 알고리즘 greedy algorithm

각각의 단계에서 최적의 수를 찾아내는 매우 간단한 알고리즘이다.

구현이 간단하다는 것이 장점
각 단계에서 국소 최적해(locally optimal solution)를 찾음으로써, 최종적으로 전역 최적해(globally optimal solution)를 구하게 된다.
- 전역 최적화를 목표로 국소 최적화를 한다.
탐욕 알고리즘은 항상 '정답'을 구하지는 못한다.
- 하지만 정답에 가까운 답을 빠른 속도로 낼 수 있다.
너비 우선 탐색, 다익스트라 알고리즘이 탐욕 알고리즘에 포함된다.

집합 커버링 문제 set-covering problem

미국의 50개 주를 모두 커버하는 방송을 하기 위해, 필요한 방송국을 방문해야 한다.

50개 주 전체를 커버하는 가장 적은 수의 방송국 집합은 어떻게 구하는가?

정답을 구하는 방법
- 가능한 모든 방송국의 부분집합을 나열함 (멱집합 power set) - 2의 n제곱 개가 된다.
- 이 멱집합 중 50개 주 전체를 커버할 수 있으면서, 가장 원소의 수가 적은 부분집합을 고른다.
- 단점 : 시간이 엄청나게 많이 걸린다. O(2의n제곱)
- 방송국의 수가 늘어날수록 전체 시간이 엄청나게 증가한다
- 이 문제에 대해 충분하 빠른 속도를 가진 알고리즘은 존재하지 않는다.

근사 알고리즘 approximation algorithm

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

근사 알고리즘의 성능 판단 기준

얼마나 빠른가
최적해(정답)에 얼마나 가까운가

탐욕 알고리즘은 구현이 쉬우면서 속도가 빠르기 때문에, 좋은 근사 알고리즘이다.

집합 (셋, set)

리스트와 비슷하지만, 중복된 원소를 가지지 않는다.

파이썬에서는 set(["a", "b", "c"])와 같이 배열을 넣어 집합을 만든다.
교집합 : &
차집합 : -

탐욕 알고리즘으로 집합 커버링 문제 풀기

준비 코드

방송하고자 하는 주의 목록
- 집합(set)으로 저장

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"])

방문할 방송국의 목록
- 집합(set)으로 저장

best_station = None
states_covered = set() ## 아직 방송되지 않은 주 중 해당 방송국이 커버하는 주의 집합
for station, states_for_station in stations.items():
    covered = states_needed & states_for_station ## 두 set의 교집합
    if len(covered) < len(states_covered): ## 더 많이 커버하는 방송국을 best_station으로 둔다
        best_station = station
        states_covered = covered

전체 코드

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 ## states_needed 갱신(이미 커버된 주 삭제)
    final_stations.add(best_station) ## 방송국 목록에 추가

NP-완전 문제 NP-complete problem

예 : 외판원 문제(팩토리얼 함수), 집합 커버링 문제

공통점 - 모든 가능한 경우를 다 따져서 최단거리/최소의 경우를 구해야 한다.

이런 문제를 NP-완전 문제라고 한다.

어렵다.
빨리 해결할 수 있는 알고리즘이 존재하지 않는다.

NP-완전 문제가 주어질 경우, 근사 알고리즘을 쓰는 것이 최선이다.

NP-완전 문제 판별법

풀려고 하는 문제가 NP-완전 문제인지 아닌지 알아내는 것은 중요하다.

왜? NP-완전 문제라면 문제를 완벽하게 풀려는 노력을 멈추고, 대신 근사 알고리즘을 통해 해결하는 게 낫기 때문.

but.. NP-완전 문제 판별법은 존재하지 않는다.

참고사항 - 아래의 경우에 해당할 경우 NP-완전 문제일 가능성이 높아진다.

항목이 적을 때는 알고리즘이 빠른데, 항목이 늘어나면서 갑자기 느려지는 경우
"X의 모든 조합"을 구하는 문제는 보통 NP-완전 문제이다.
더 작은 하위 문제로 변환할 수 없어서, X의 가능한 모든 버전을 계산해야 한다면 NP-완전 문제일 가능성이 높다
문제가 수열(ex.외판원 문제)을 포함하고, 풀기가 어려우면 NP-완전 문제일 수 있다
문제에 집합(ex.집합 커버링 문제)이 있고, 풀기가 어려우면 NP-완전 문제일 수 있다
문제를 집합 커버링 문제나 외판원 문제로 재정의할 수 있다면, 명백하게 NP-완전 문제이다.

Bibi

이전 포스트

[Hello Coding 알고리즘] 7. 다익스트라 알고리즘 Dijkstra's algorithm

다음 포스트

[Hello Coding 알고리즘] 8. 탐욕 알고리즘 greedy algorithm