greedy.md

Greedy Algorithm

Greedy 알고리즘 이란?

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

Greedy 알고리즘 예제

5개의 도시가 존재하고 1번도시에서 5번도시까지 가는데 도시들을 한번 씩만 거쳐 가는 경우 각 길에는 비용이 존재한다고 하면 최저의 비용으로 5번도시로 가능 비용을 구하려고 한다.

이러한 경우 그리디 알고리즘을 사용하면 1번 도시 부터 연결되어 있는 도시 중 가장 비용이 적은 길을 선택하여 다음 도시로 이동 한다. 이러한 과정을 반복하여 5번도시 까지 이동한다.

여기서 선택된 길들의 비용이 1 - 1 - 1 - 100 이라고 할 때, 이것이 과연 최적의 답이냐고 물어본다면 그럴수도 있고 아닐 수도 있고이다. 즉 각 순간순간의 최적의 답을 구한다고 무조건적으로 전체에 최적의 답이라는 것은 보장할 수 없다는 것이다. 예를들면 순간순간의 최적의 답을 구한 1 - 1 - 1- 100 이 아닌 3번째 길을 다른 길을 선택했다면 1 - 1 - 10 - 10 이라는 더욱 최적의 답이 나올 수 있는 것이다. 즉 3번째 길을 순간의 최적이 아닌 다른 길을 선택했더니 더욱 최적의 결과가 나온 것이다.

Greedy 알고리즘 사용

위와 같이 순간의 최적을 구한다고 종합적인 최적을 구할 수 있다고 보장 할 수 없다면 해당 알고리즘은 언제 어떻게 사용 해야 할까? 다음과 같은 경우에 사용 할 수 있다.

• 탐욕 선택 속성(greedy choice property)
• 최적 부분 구조(optimal substructure)

탐욕 선택 속성이란 한번의 선택이 다음 선택에 아무런 영향을 끼치지 않는 것을 말한다.

최적 부분 구조란 매순간의 최적해의 집합이 전체 문제에 대한 최적해여야 하는 것을 말한다.

Greedy 알고리즘 사용 예시

• AI에 있어서 결정 트리 학습법(Decision Tree Learning)
• 활동 선택 문제(Activity selection problem)
• 거스름돈 문제
• 최소 신장 트리 (Minimum spanning tree)
• 제약조건이 많은 대부분의 문제
• 다익스트라 알고리즘
• 허프만 코드
• 크루스칼 알고리즘

Greedy 알고리즘으로 최적해를 구할 수 없는 문제

• 외판원 순회 문제 (TSP, Traveling Salesperson Problem)
• 배낭 문제 (Knapsack Problem)

Reference 나무위키(그리디 알고리즘)