그리디(Greedy)
1. 당장 좋은 것만 선택하는 그리디
2. 큰 수의 법칙
3. 숫자 카드 게임
4. 1이 될 때까지
1️⃣ 당장 좋은 것만 선택하는 그리디
그리디 알고리즘(탐욕법)
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 매 순간 가장 좋아보이는 것을 선택, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
- 기준에 따라 좋은 것을 선택하는 알고리즘 누제
- 가장 큰 순서대로
- 가장 작은 순서대로
- 주로 정렬 알고리즘과 출제
예제 3-1) 거스름돈
Q) 당신은 음식점의 계산을 도와주는 점원이다. 카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
A) 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제 -> '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것
N원을 500원으로 거슬러 줄 수 있는 만큼 -> 100원 -> 50원 -> 10짜리 순서
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)화폐의 종류만큼 반복을 수행 -> 화페의 종류가 K개이면 시간 복잡도는 O(K) -> 동전의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있음.
그리디 알고리즘의 정당성
- 그리디 알고리즘으로 문제의 해법을 찾으면 그 해법이 정당한지 검토해야함
- 거스름돈 문제를 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문임
- 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있음