1. 그리디 (Greedy) 알고리즘
탐욕법(Greedy)은 현재 상황에서 가장 좋은 것만 고르는 방법을 의미한다.
그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
그리디 알고리즘의 특징은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이다. 즉, 다른 알고리즘의 경우에는 알고리즘의 사용 방법을 정확히 알고 있어야 한다. 그리디 알고리즘의 문제는 매우 다양하기 때문에 많은 유형을 접해보고 문제를 많이 풀어보면서 감을 익혀야 한다. 보통 창의력을 요구하기 때문에, 문제에서 단순히 현재 상황에서 가장 좋아 보이는 것만 선택해도 문제를 풀 수 있는지 파악해야 한다.
보통 그리디 알고리즘의 문제의 경우, 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 슬쩍 제시해준다. 이는 정렬 알고리즘을 사용했을 때 만족시킬 수 있기 때문에 그리디와 정렬은 짝꿍이라고 생각하자.
2. 예제 문제
(1) 거스름돈
거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
=> 가장 큰 화폐 단위부터 돈을 거슬러 주자!
n = 1260
cnt = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
cnt += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(cnt)=> 위의 코드는 화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 N개라고 할 때, 시간복잡도는 O(N)이다. 참고로 시간복잡도에서 거슬러 주어야 할 돈은 찾아볼 수 없다. 즉, 이 알고리즘의 시간복잡도는 동전의 총 종류에만 영향을 받고, 거슬러줘야 하는 금액의 크기와는 무관한다.
3. 활용
다익스트라 알고리즘: 최단 경로 문제크루스칼 알고리즘,프림 알고리즘: 최소 신장 트리 문제작업 스케줄링 문제
Huffman
4. 문제
Reference
이것이 코딩테스트다 with 파이썬