그리디 알고리즘
덤프버전 :
분류
1. 정의[편집]
그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.[1]
예를 들어 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자.[2] 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.
단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 위의 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다.
그리디 알고리즘을 한마디로 설명한다면 그 유명한
그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 위 서술 같은 경우는 그리디 알고리즘으로 해결 할 수 없는 문제에 그리디 알고리즘을 적용한 경우니 당연히 최적해를 보장해주지 못한다.
2. 특징[편집]
그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.
예를 들어서 상기 교차로 문제는 도로가 어떻게 생겼는지에 따라서 다음 선택에 영향이 가며, 만일 두 수가 매 턴에 주어지고 종료시에 모든 선택된 수의 합이 최대로 하고자 하면 그냥 매 단계에서 두 숫자 중 큰 숫자를 고르면 매 순간의 최적해의 set이 최종적으로 문제의 최적해라고 볼 수 있다는 의미이다.
2.1. 최적 부분 구조[편집]
최적 부분 구조를 좀 더 살펴보면 그림과 같이 설명할 수 있다. 서울에서 대구를 거쳐 부산까지 가는 최단 경로를 찾는다고 가정해보자. 그림에서 보듯이, 서울에서 대구까지 가는 경로는 3가지가 있으며, 부산까지도 마찬가지로 3가지 경로가 있다. 서울에서 부산까지 가는 최단 경로는 200km + 80km = 280km이다. 이 경로는 서울에서 대구까지 가는 최단 경로(200km)와 대구에서 부산까지 가는 최단 경로(80km)로 구성된다. 즉, 서울에서 대구를 거쳐 부산까지 가는 최단 경로는 각각의 부분 문제인 1)서울에서 대구까지 가는 최단 경로 문제와 2)대구에서 부산까지 가는 최단 경로 문제의 해결 방법의 합이다. 따라서 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다. 이러한 구조를 최적 부분 구조라 한다.
3. 근사 알고리즘[편집]
상기했다시피 그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 다만, 어느 정도 적합한 수준의 해답을 알려준다. 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을 때에는 사용할 수 있다. 특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기 때문에 실용적으로 사용이 가능하다. 허나 이게 정말로 "적당히" 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다. 또한, 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수가 있다.[3]
4. 예시[편집]
- 결정 트리 학습(Decision Tree Learning)
- 활동 선택 문제(Activity selection problem)
- 거스름돈 문제[4]
- 최소 신장 트리(Minimum spanning tree)
- 제약조건이 많은 대부분의 문제[5]
- 다익스트라 알고리즘
- 허프만 코드
- 크루스칼 알고리즘
5. 최적값을 구하는 데 실패하는 문제들[편집]
이 문서의 내용 중 전체 또는 일부는 2023-11-14 22:13:35에 나무위키 그리디 알고리즘 문서에서 가져왔습니다.[1] 정치적으로 보면 당면한 경제 문제를 가장 빠르게 해결해 줄 것이라고 여기는 대통령을 찍거나 당면한 지역 인프라 과제를 가장 빠르게 해결해 줄 것이라고 여기는 시장·군수·도지사 또는 국회의원을 찍는 의사결정 행위로 볼 수 있다.[2] 이는 일반적으로 외판원 순회 문제 (Traveling Salseperson Problem, TSP)로 알려져 있다.[3] 가지치기[4] 단, 동전들에 배수관계가 성립할 때만 한정. 대부분의 화폐는 1, 5, 10, 25, 50 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디로 해결된다.[5] 항상 그런 것은 아니지만, 프로그래밍 문제를 풀 때 제약조건이 많다면 대부분 그리디로 풀리는 경우가 많다. 다만 그리디인 줄 알고 풀었다가 피보는 경우도 있다.