[알고리즘] 1. 그리디 - 개념 및 도입

코테에서의 그리디는

• 창의력(=최소한의 아이디어 떠올림)
• 판단력(=현재 상황에서 가장 좋아보이는것을 선택해도 문제를 풀 수 있는 것을 보장하는가)
  를 요구한다.

대표예시 : 거스름돈

n = 1260
cnt = 0

# 가장 큰 단위의 화폐부터 차례대로 확인
coin_type = [500, 100, 50, 10]

for coin in coin_types :
	count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 갯수 세기
    n %= coin
    
print(count)

거스름돈 문제가 그리디로 해결 가능한 이유는
가지고 있는 동전 중에서 큰 단위 = 항상 작은 단위의 배수.
그러므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

ex) 500, 400, 100원을 가지고 800원을 만들때
500은 400의 배수가 아니다.
그러므로 그리디로 풀게되면 500+100+100+100 이 되는데,
최적의 해는 400+400 임.

이처럼 문제풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토해야 한다.

처음 문제를 만났을때

• 바로 문제 유형을 파악하기 힘들다면 그리디를 의심
• 오래 고민해도 그리디가 아닌 것 같다면 DP나 그래프 알고리즘일지 재차 고민
• 다양한 아이디어를 고려하자
  '10원짜리로만 거슬러준다면?'
  '10원짜리로만 하면 최적의 해가 아니구나'
  ....
  '가장 큰 단위부터 가장 작은 단위까지 거슬러준다면?'
  '항상 최적의 해를 보장할 수 있겠구나!'
  

모든 거스름돈 문제는 그리디?

동전 단위가 배수 형태가 아닌 무작위일때 DP
그리디는 늘 최적의 해를 보장함을 검증해야만한다!