그리디
그리디
그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 방법으로 불리는 알고리즘 패러다임이다.
최적해를 구하기 위해 전후 단계에서의 선택은 고려하지 않고 각 단계마다 정해진 기준에 따라 가장 최선이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법이다.
그리디 방법을 적용하면 오직 현 시점에서의 최적해만을 고려하기 때문에 항상 전체적인 최적해를 만들지 못할 수도 있음을 인지해야 한다.
이처럼 제한적인 적용 범위라는 한계가 있지만, 어떤 문제에 대해 그리디 방법을 적용할 수 있음이 파악된다면 최적해를 보장하는 효율적이며 간단한 알고리즘을 설계할 수 있는 기법이다.
예제
그리디 방법이 적용된 대표적인 알고리즘은 거스름돈 문제 또는 배낭 문제와 같은 간단한 문제에서부터 최소 신장 트리를 구하는 크루스칼 알고리즘, 그리고 단일 출발점에 대해 최단 경로를 구하는 데이크스트라 알고리즘 등이 있다.
거스름돈 문제
동전의 종류가 500원, 100원, 50원, 10원 다섯 가지의 종류가 있을 때, 거스름돈이 780원이면 고객에게 돌려줄 수 있는 동전의 최소 개수를 구하라
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def coinChange(change: int) -> int:
count = 0
while change >= 500:
change -= 500
count += 1
while change >= 100:
change -= 100
count += 1
while change >= 50:
change -= 50
count += 1
while change >= 10:
change -= 10
count += 1
return count
위와 같이 알고리즘을 설계하면 위에서부터 큰 값의 동전부터 하나씩 돌려주는 셈이라 최적해를 구할 수 있다.
그리디 알고리즘을 적용할 때 대표적으로 주의해야 하는 것이 있는데, 작은 값은 큰 수의 약수여야 한다는 점이다.
이게 무슨 말이냐면, 500원, 100원, 50원, 10원으로 보여지는 동전 액면가들은 서로의 배수이자 약수라는 것이다.
이런 경우에 한해서 최적해를 구할 수 있으며, 동전의 액면가가 120원인 동전이 있다고 가정하면 그리디 방법으로는 최적해를 구할 수 없다.
배낭 문제
n개의 물건과 각 물건의 무게와 가치 w와 v가 주어지며, 각 물건이 최대 m만큼 있을 때 용량이 k인 배낭에 용량을 초과하지 않고 담을 수 있는 물건의 최대 가치를 찾아라.
배낭 문제에는 대표적으로 두 가지 종류가 있다:
- 분할 가능 배낭 문제
- 0-1 배낭 문제
0-1 배낭 문제는 물건을 넣느냐 마느냐를 선택을 해야하는 문제이며 물건의 일부를 넣을 수는 없다.
이는 그리디 방법으로 해결이 안되며 동적계획법을 사용하여 해결해야 한다.
반면, 분할 가능 배낭 문제는 그리디 방법을 적용하여 해결이 가능하다:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from typing import List, Tuple
class Item:
def __init__(self, value: float, weight: float):
self.value = value
self.weight = weight
def fractional_knapsack(items: List[Item], capacity: float) -> float:
items.sort(key=lambda x: x.value / x.weight, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
capacity -= item.weight
total_value += item.value
else:
total_value += item.value * (capacity / item.weight)
break
return total_value