그리디 알고리즘이란?
탐욕 알고리즘 또는 그리디 알고리즘(greedy algorithm)은 문제를 해결할 때 매 순간 가장 최적이라고 생각되는 선택을 하는 알고리즘 설계 기법입니다. 이러한 선택은 그 순간에 대해서는 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없습니다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들입니다.
그리디(greedy) 알고리즘은 말그대로 탐욕스럽게 미래를 생각하지 않고
현재에서 매 순간 최선의 선택을 하면서 답을 구하는 알고리즘입니다.
특징
- 단순성: 구현이 비교적 간단하며 이해하기 쉽습니다.
- 빠른 실행 속도: 복잡한 연산이 필요하지 않아 실행 속도가 빠릅니다.
- 최적해 보장 여부: 모든 문제에서 최적해를 보장하지는 않으므로 적용 가능 여부를 판단해야 합니다.
💡 예시 : 거스름돈 문제
문제 설명:
어떤 가게에서 거스름돈으로 줄 수 있는 동전의 종류는 500원, 100원, 50원, 10원입니다. 손님에게 거슬러줘야 할 금액이 N원일 때, 동전의 최소 개수를 구하는 프로그램을 작성하세요.
그리디 알고리즘 적용 방법:
- 가장 큰 단위의 동전부터 사용합니다.
- 현재 동전으로 거슬러줄 수 있는 만큼 최대한 거슬러 줍니다.
- 남은 금액에 대해 다음으로 큰 단위의 동전으로 반복합니다.
예시 코드 (Python):
def get_min_coin_count(n, coin_types):
count = 0
for coin in coin_types:
count += n // coin # 해당 동전으로 거슬러 줄 수 있는 개수
n %= coin # 거슬러 주고 남은 금액
return count
n = 1260
coin_types = [500, 100, 50, 10]
print(get_min_coin_count(n, coin_types)) # 출력: 6실행 결과 설명:
- 500원 동전 2개: 1000원
- 100원 동전 2개: 200원
- 50원 동전 1개: 50원
- 10원 동전 1개: 10원
- 총 동전 개수: 6개
주의사항
그리디 알고리즘이 항상 최적해를 보장하지 않는 경우
동전 단위가 서로 배수 관계가 아닐 때는 그리디 알고리즘이 최적해를 보장하지 않습니다.
최적해란? 주어진 문제에서 가장 최소 또는 최대 값을 구하는 것
예시 문제:
동전의 종류가 500원, 400원, 100원이고, 거스름돈이 800원이라면?
그리디 알고리즘 적용 결과:
- 500원 1개 사용 → 남은 금액 300원
- 100원 3개 사용 → 남은 금액 0원
- 총 동전 개수: 4개
최적해:
- 400원 동전 2개 사용 → 남은 금액 0원
- 총 동전 개수: 2개
그리디 알고리즘을 적용했을 때보다 동전 개수가 적으므로, 이 경우 그리디 알고리즘은 최적해를 구하지 못합니다.
그리디 알고리즘 적용 가능한 문제 유형
- 활동 선택 문제: 일정 시간에 가장 많은 활동을 선택하는 문제.
- 최소 신장 트리: Kruskal 알고리즘, Prim 알고리즘.
- 허프만 코딩: 데이터 압축에 사용하는 알고리즘.
결론
그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 방법으로, 문제에 따라 매우 효율적이고 간단한 해결책을 제공합니다. 하지만 항상 최적해를 보장하지는 않으므로, 해당 알고리즘이 문제에 적합한지 판단하는 것이 중요합니다.
참고
https://night-knight.tistory.com/entry/그리디Greedy-알고리즘-예시와-문제
https://ko.wikipedia.org/wiki/탐욕_알고리즘
