1. 그리디 알고리즘 (Greedy Algorithm) ?
현재 상황에서 지금 당장 좋은 것만 고르자
그리디 알고리즘은 이름 그대로 다양한 알고리즘 교재나 문서에서 "탐욕법"으로 소개되고 있는 알고리즘입니다.
탐욕적으로 매 순간 가장 좋은 것을 선택하고, 선택이 미래에 미칠 영향은 고려하지 않습니다.
그렇기 때문에 그리디 알고리즘은 최종적인 결과 도출에 대한 최적해를 보장하지 않습니다.
하지만 그리디 알고리즘은 간단하고 빠르기 때문에 해결할 문제가 그리디 알고리즘을 사용할 조건을 갖출 때 사용합니다.
즉, 그리디 알고리즘을 사용했을 때 최적의 해를 구할 수 있는 문제일 때 입니다.
2. 그리디 알고리즘의 정당성 판단
그리디 알고리즘이 최적의 해를 구할 수 있는 조건은 아래의 두 가지입니다.
- 탐욕 선택 속성 (greedy choice property)
- 최적 부분 구조 (optimal substructure)
탐욕 선택 속성은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이고,
최적 부분 구조는 전체 문제에 대한 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성된다는 것입니다.
위의 조건을 만족하지 못하는 문제에서는 그리디 알고리즘이 최적의 해를 구하지 못합니다.
하지만 이러한 경우에 그리디 알고리즘은 속도가 빠르기 때문에 근사 알고리즘으로 사용되어 어느 정도 적합한 해를 구할 때 사용될 수 있습니다.
❓ 근사 알고리즘 (Approximation Algorithm)❓
- 어떠한 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
그렇기 때문에 문제를 풀 때 그리디 알고리즘으로 문제를 해결했다면 그 조건이 성립하는지, 그 방법이 정당한지 검토해야 합니다.
3. 대표적인 예시 - 거스름돈 문제
카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다.
이때 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.
단, 거슬러 줘야 할 돈 N은 항상 10의 배수
위 문제에서 우리가 가장 쉽게 떠올릴 수 있는 해결 방법은 가장 큰 단위의 돈부터 거슬러주는 것입니다.
만약 거슬러 주어야 할 돈이 1620원이라고 해보겠습니다.
가장 큰 단위인 500원부터 거슬러 주면 500원 3개를 거슬러 주고,
남은 120원을 100원짜리 1개로 거슬러 주고,
남은 20원을 10원짜리 2개로 거슬러 주면 됩니다.
def sol(money):
n = money
count = 0
moneyType = [500, 100, 50, 10]
for i in moneyType:
count += n // i
n %= i
return count
그리디 알고리즘으로 문제를 해결했기 때문에 위에서 설명했듯이 그 방법이 정당한지 검토해보아야 합니다.
결과적으로 이 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 거스름돈의 큰 단위가 항상 작은 단위의 배수여서 작은 단위의 돈을 조합해 다른 최적의 해가 나올 수 없기 때문입니다.