그리디 알고리즘

– Greedy Algorithm

개념

욕심쟁이라지만 사실 그때 그때 최적의 판단을 하는 거다

내일 100만원 vs 지금 10만원 느낌으로 말이다

내일 100만원 줄지 안줄지 모르니 10만원 챙기는 거다

때에 따라 최적의 답을 내놓긴 하고

어지간해선 최적 비스무리하게 답을 내놓아 선호되는 방식이다

꼭 최적이 아니더라도 효율이 중요하면 사용된다

단, 재수 없을 경우 최악의 결과를 불러오기도 하기에

때를 가려 사용해야 한다

특징

탐욕적 선택 속성(Greedy Choice Property): 현재 상태에서 가장 좋아 보이는 것을 선택
최적 부분 구조(Optimal Substructure): 부분 문제의 최적해로 전체 문제의 최적해를 구할 수 있음
보통 정렬 활용한다

예제

– 동전 거스름돈

가지고 있는 동전 종류: 500원, 100원, 50원, 10원
거슬러줘야 할 금액: 1260원
동전의 개수가 최소가 되도록 구성

가장 큰 동전부터 쓰기

그리디한 방법

코-드

def greedy_coin_change(n):
    coins = [500, 100, 50, 10]
    count = 0
    for coin in coins:
        count += n // coin  # 해당 동전 몇 개 쓸 수 있는지
        n %= coin           # 남은 금액 갱신
    return count

print(greedy_coin_change(1260))  # 출력: 6

동작 과정:

500원 × 2 → 1000원
100원 × 2 → 200원
50원 × 1 → 50원
10원 × 1 → 10원
총 6개

유의점

늘 최적이 아니라 했는데

이럴 수 가 있다

🔽🔽🔽🔽🔽

그리디 ㅈ망

동전이 500, 400, 100인데, 800원을 거슬러줘야 한다면?

그리디는 500 + 100 + 100 + 100 (총 4개)

하지만 400 + 400 = 800 (총 2개)가 더 최적임 → 그리디 실패

그러니 이를 염두에 두고 사용하자