[이코테] 그리디(Greedy, 탐욕법)

📌 그리디란? 

그리디 알고리즘은 말 그대로 지금 이 순간 가장 좋아 보이는 선택을 하는 방식으로 문제를 해결하는 알고리즘이다. 현재 단계에서 최선이라고 판단되는 해만 고르며 나중에 그 선택이 어떤 영향을 미칠지는 고려하지 않는다.

✔️ 그리디 알고리즘의 특징

1. 단순하고 직관적인 해결 방법
   • 복잡한 탐색 과정 없이 현재 상황에서 가장 좋아 보이는 해를 선택한다.
   • 그리디가 통하려면 문제 속에 숨어 있는 규칙을 찾아야 한다.
   • 즉 최소한의 아이디어만 떠올리면 훨씬 간단하게 해결되는 유형이 많다.
   • EX> 동전 거스름돈 문제에서 가장 큰 단위의 동전부터 사용하는 방식.
2. 정렬과 자주 함께 출제
   • 많은 그리디 문제는 “가장 큰 순서대로”, “가장 작은 순서대로” 등 정렬 기준을 명시적으로 또는 암시적으로 제시한다.
   • 따라서 그리디 문제는 대체로 정렬 → 규칙 발견 → 반복 수행 구조로 해결되는 경우가 많다.

❓ 모든 문제에 그리디를 적용할 수 있을까?

정답은 NO다.

그리디 알고리즘은 매 순간의 선택이 전체 최적해로 이어지지 않을 가능성이 매우 높다. 따라서 그리디 알고리즘을 적용할 때 가장 중요한 것은 정당성 검토이다.

 

---

📝예제> 거스름돈

 

문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 죄소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

답안 예시

# 거스름돈 금액 입력 (예: 1260)
n = int(input())

coins = [500, 100, 50, 10]  # 큰 단위부터 정렬
count = 0  # 필요한 동전 개수

for coin in coins:
    count += n // coin   # 해당 동전이 몇 개 필요한지
    n %= coin            # 그만큼 거스르고 남은 금액으로 갱신

print(count)

 

🔴Reference

이것이 취업을 위한 코딩테스트다 with 파이썬 - 나동빈 저