1. 탐욕 알고리즘이란?
탐욕 알고리즘이란 각 순환마다 '가장 좋은' 선택을 합니다.
탐욕 알고리즘은 DP와 마찬가지로 최적화 문제를 푸는데 주로 사용됩니다. 또한 상대적으로 DP보다 알고리즘을 설계하기 더 쉽습니다.
DP는 재귀 관계식을 세워서 큰 instance를 작은 instance로 분할해서 문제를 풉니다.
하지만 탐욕법은 instance를 분할하지 않습니다.
단지 순서대로 가장 좋아 보이는 답을 선택해서 모읍니다.
즉, 어떤 선택이든지 선택할 당시에는 최적입니다. (locally optimal)
하지만 이게 곧 전체에서 최적인 해 (globally optimal)를 구한다는 보장은 없습니다.
따라서 탐욕법은 해당 알고리즘이 최적의 해답을 얻는지 확인하는 절차를 반드시 거쳐야 합니다.
DP는 최적의 해답이 있을 때, 부분적으로도 최적인지를 알아봤었죠?
탐욕법의 한 가지 예를 들어보겠습니다.
물건을 사면 거슬러 줘야 합니다. 만약 거스름돈이 870원인데 10원짜리 87개를 거슬러주면 싸움 나겠죠?
따라서 저희의 목표는 최대한 적은 양의 동전을 주는 것입니다.
그러면 당연히 500원을 먼저 주고, 370원이 남았으므로 100원짜리 3개를 주겠죠?
이런 방식으로 큰 동전을 먼저 거슬러 주고, 이 값이 거슬러주어야 할 액수를 초과하지 않는다면 다시 처음으로 돌아와서 거슬러줍니다.
즉, 탐욕법의 방식은 아래와 같습니다.
- Selection procedure : 가장 큰 액수의 동전을 고른다
- Feasiblity check : 거스름돈의 총액이 거슬러주어야 할 액수를 넘지 않는다면, 방금 고른 동전을 거스름돈에 추가한다.
- Solution check : 거스름돈의 총액이 거슬러주어야 할 액수와 같은지 검사한다. 만약 같지 않다면 selection procedure로 돌아가서 이 작업을 반복한다.
- 이때 solution check는 거스름돈의 총액이 거슬러주어야 할 액수와 같거나,
- 동전이 다 떨어질 때까지 반복한다.
- 즉, feasibility 하지 않거나, solution을 찾으면 종료된다.
쉽게 이해가 되시나요?
가장 좋아 보이는 선택을 하고, 이 선택을 실행할 수 있는지를 체크합니다. 이후 실행 가능하다면 실행을 하고, 해결했는지 알아봅니다.
만약 해결했다면 그대로 종료, 아니라면 다시 반복합니다.
만약 selection procedure에서 큰 액수의 동전을 골랐는데, 이를 추가한 거스름돈의 총액이 거슬러주어야 할 액수를 초과한다면, 집은 동전은 다시 내려놓아야 합니다.
이 알고리즘이 '탐욕법'인 이유는 selection procedure에서 발생하는 잠재적인 결함을 고려하지 않고, 무작정 선택하기 때문입니다.
이 과정은 매우 간단하지만, 과연 이렇게 얻은 답이 최적일까요? ㅎㅎ
즉, 거스름돈 문제에서 탐욕법으로 구한 거스름돈의 동전 개수가 최소일까요?
만약에 우리나라의 원 단위로 탐욕법을 쓴다면 최적입니다. ㅎㅎ
또한 미국의 달러를 써도 마찬가지입니다.
하지만 여기서 어떤 조건을 추가한다면 탐욕법을 썼을 때의 최적과 globally optimal은 달라지게 됩니다.
2. 탐욕법의 반례와 이유
만약에 16원을 거슬러 주어야한다고 가정해봅시다.
이때 우리는 돈 [12원, 10원, 5원, 1원] 이렇게 가지고 있습니다.
탐욕법을 쓰면 어떻게 될까요?
[12원, 1원, 1원, 1원, 1원]이 되겠죠?
근데 저희는 이게 최적이 아닌걸 알고 있습니다.
바로 최적은 [10원, 5원, 1원]입니다.
위 문제에서 보듯이 탐욕법은 항상 최적의 해를 보장하지 않습니다.
왜 12원을 추가하면 탐욕법이 최적의 해가 아닐까요?
이유는 간단합니다.
가장 비싼 동전이 다른 동전의 배수가 아니기 때문입니다.
따라서 1원 동전을 10개 쓸 바에 10원 동전을 하나 쓰는게 낫습니다.
3. 탐욕 알고리즘 정리
탐욕법은 공집합에서 시작하여, 집합이 문제의 해답이 될 때까지 원소를 집합에 추가합니다.
- Selection Procedure : choose the next item to add to the set (최적을 선택하는 기준에 따라)
- Feasibility Check : determines if the new set feasible (새로운 집합이 해답이 되기 적절한지 검사)
- Solution Check : determines wheter the new set constitutes a solution (새로운 집합이 해답인지 결정)
감사합니다.
지적 환영합니다.