탐욕 알고리즘 (Greedy algorithm)

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 “매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자” 라는 모토를 가지는 알고리즘 설계 기법이다. 기술적 용어로 말하자면 각 단계에서 국소 최적해를 찾음으로써 최종적으로는 전역 최적해를 구하게 된다.

예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자. 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 “지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다”라는 방법이 될 수 있다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.

• 탐욕 알고리즘이 항상 성공하는 건 아니지만, 간단해서 구현하기 좋다.
• 탐욕 알고리즘은 전역 최적화를 목표로 하지만, 실제로는 국소 최적화를 한다.

근사 알고리즘

그리디 알고리즘은 정답을 줄 수는 없어도, 정답에 상당히 가까운 답을 준다. 이런 알고리즘을 근사 알고리즘(approximation algorithm)이라고 한다. 근사 알고리즘의 성능은 다음 두 가지로 판단한다.

• 얼마나 빠른가
• 최적해에 얼마나 가까운가

탐욕 알고리즘은 다루기 간단하고, 그 단순함으로 인해 실행 속도가 빠르기 때문에 좋은 선택이 될 수 있다. 이 경우에 탐욕 알고리즘의 실행 속도는 O(n^2) 시간이다.

NP-완전 문제

모든 가능한 경우를 다 따져서 최단/최소를 구해야 하는 문제다. NP-완전 문제는 어렵다. 만약 NP-완전 문제를 만난다면 문제를 완벽하게 풀려는 노력을 멈추고 근사 알고리즘을 써서 풀어야 한다. 하지만 어떤 문제가 NP-완전인지를 아는 것은 어려운 일이다. 보통 쉽게 풀리는 문제와 NP-완전 문제 사이에서는 조그만 차이밖에 없기 때문이다.

NP-완전 문제인지 아닌지 알 수 있는 쉬운 방법은 존재하지 않지만, 다음과 같이 몇 가지 참고 사항은 있다.

• 항목이 적을 때는 알고리즘이 빠른데, 항목이 늘어나면서 갑자기 느려진다.
• “X의 모든 조합”이라고 하면 보통 NP-완전 문제이다.
• 더 작은 하위 문제로 변환할 수 없어서 X의 가능한 모든 버전을 계산해야 한다면 아마도 NP-완전 문제일 것이다.
• 문제가 수열(외판원 문제와 같은 도시의 순서같이)을 포함하고 풀기가 어려우면 NP-완전 문제일 수 있다
• 만약 문제에 집합(라디오 방송국 집합처럼)이 있고 풀기가 어려우면 NP-완전 문제일 수 있다.
• 문제를 집합 커버링 문제나 외판원 문제로 재정의할 수 있다면, 명백하게 NP-완전 문제이다.

그리디 알고리즘의 예제

최대한 적은 수의 방송국으로 모든 주를 커버하는 방법

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문 밖에 있는 이유: 계속 best_station 을 찾고 final_stations 에 넣어야 결과가 안 없어진다.
# 그래야 while 문 밖에 있는 곳에서도 접근할 수 있고
# while 문 속에 final_stations = set()이 있으면 계속 초기화 되서 결과가 날아간다.

while states_needed:
    best_station = None  # 가장 많은 주를 커버할수 있는 방송국을 저장
    states_covered = set()  # 지금 찾고 있는 방송국이 커버하는 주를 저장

    for station, states in stations.items():  # 키, 데이터  # 방송국을 하나씩 꺼내면서 연산 진행
        # 교집합 # states_needed의 주중에서 방송국이 커버하는것을 저장. 해당 방송국이 커버하는 주 갱신
        covered = states_needed & states

        if len(covered) > len(states_covered):  # best_station 보다 더 많은 주를 커버하는지 확인
            best_station = station
            states_covered = covered

    states_needed -= states_covered  # states_needed 가 완전히 빌 때까지 반복
    final_stations.add(best_station)  # best_station 을 추가

print("최대한 적은 수로 모든 주를 커버하는 방송국은 : ")
print(final_stations)
# {'kfive', 'kthree', 'ktwo', 'kone'}

References

• 그림으로 개념을 이해하는 알고리즘
• https://namu.wiki/w/그리디%20알고리즘