그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm)은 전략을 따르는 알고리즘 설계 기법

지금 당장 가장 좋아 보이는 선택을 하면서 문제를 해결해 나가는 방식

 

조건

알고리즘이 정확한 해답을 보장하려면 다음 두 가지 조건을 만족해야 함

1. 탐욕 선택 속성(Greedy Choice Property)
   • 지금의 선택이 미래의 선택과 독립적
2. 최적 부분 구조(Optimal Substructure)
   • 전체 문제의 최적해가 부분 문제의 최적해들로 구성될 수 있다

그리디가 안 되는 예시: 외판원 문제(ISP)

• 현재 위치에서 가장 가까운 도시로만 이동하면 전체 경로는 반드시 최단이 되지 않음

 

그리디 알고리즘은 정답이 보장되는 구조에서만 강력한 무기가 될 수 있다

코드 리뷰

동전 거스름 문제

• 당신은 1000원을 거슬러줘야 함
  사용할 수 있는 동전은 [500, 100, 50, 10]원
  동전 개수를 최소로 사용하기

그리디 전략 -> 가장 큰 단위의 동전부터 최대한 많이 사용

def coin_change_greedy(amount, coins=[500, 100, 50, 10]):
    count = 0
    for coin in coins:
        num = amount // coin  # 해당 동전 몇 개 쓸 수 있는지
        count += num
        amount -= num * coin  # 남은 금액 업데이트
    return count

print(coin_change_greedy(1000))  # 출력: 2 (500*2)