Greedy

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해 고려하지 않는다.
• 단순 무식하게. 탐욕적으로 문제를 푸는 알고리즘
  → 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준 제시

📌 Greedy Algorithm 필요 조건

1. 탐욕스러운 선택 속성(Greedy choice property)
   • 탐욕적인 선택이 안전해야 함.
   • 각각의 탐욕적인 선택을 바탕으로 최적해를 구할 수 있어야 함.
2. 최적 부분 구조(Optimal substructure)
   • "문제에 대한 최적해를 구하는 방법이 하위 부분 문제에 대해서도 최적해의 방법" 조건 충족.
   • 모든 문제는 부분 문제로 이루어져 있으며, 해당 부분 문제의 최적해가 도출되어야 함.

📌 Greedy vs Dynamic Programming

Greedy

• 풀이 속도 : 답을 구하는 과정이 빠름
• 최적해 : 한정된 조건에서만 최적해 도출 가능
• ex) MST(최소 신장 트리), Dijkstra

Dynamic Programming

• 풀이 속도 : 점화식 도출 과정에서 풀이 속도가 비교적 느림
• 최적해 : 최적해 도출 가능
• ex) 피보나치 수열

📌 Greedy example

• ex) 거스름돈 예시

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

• 1st solution : 가장 큰 화폐 단위부터 돈을 거슬러 주는 것
  → 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)$
• 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수 → 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.
  → 그리디 알고리즘 풀이 : 문제 풀이를 위한 최소한의 아이디어를 떠올린 뒤 이것이 정당한지 검토할 수 있어야 한다.