Greedy

Greedy

Greedy는 말 그대로 탐욕, 즉 현재 상황만을 보고 그 순간 순간 할 수 있는 최고의 선택을 하는 것을 의미한다. 그리디 문제는 정형화된 틀이 존재하지 않는다. 어떠한 정해진 알고리즘이 있는 것이 아니라 조건에 맞추어 순간순간 할 수 있는 최고의 선택을 하여 답을 추론하는 방식이다.

Example

예를 들어, 아래와 같은 문제가 있다고 가정하자.

Q1: 카운터에 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정할때, 손님에게 N원을 거슬러 주려고 할 때 동전의 개수를 최소가 되도록해라.

이런 문제가 있을 경우, 어떻게 해결하는 것이 가장 최선일까? ==> 큰 화폐 단위부터 거슬러 주게 되면 문제를 쉽게 해결 할 수 있다.

n=int(input())

money_types=[500,100,50,10]
count=0
for money_type in money_types:
  count+=(n)//money_type
  n%=money_type

print(count)

하지만 만약 문제가 이렇게 주어지면 어떻게 될까?

Q2: 카운터에 500원, 400원, 100원, 50원짜리 동전이 무한히 있다고 가정할때, 손님에게 N원을 거슬러 주려고 할 때 동전의 개수를 최소가 되도록해라.

만약 그리디 방법으로 800원을 거슬러 주려고 하면 4개의 동전이 쓰인다(500+100+100+100) 하지만 최적의 방법은 2개의 동전을 쓰는 것이다.(400+400)

1번 문제의 경우 화폐의 단위가 큰 단위가 작은 단위의 배수로 이루어져있기 때문에 항상 큰 단위를 사용하는 것이 무조건 좋지만, 아래와 같은 문제는 배수로 되어 있지 않고 무작위로 되어 있기 때문에 오히려 작은 단위의 화폐를 사용했을 때 최적의 해안이 나올 수 도 있다.

2번 문제 같은 경우는 아래와 같이 D.P 방식으로 접근해야 한다.

from math import inf
n=int(input())
dp=[inf] * (n+1)

 dp[0]=0

for i in range(10,n+1,10):
  temp=inf
  if i >=500:
    temp=min(temp,dp[i-500])
  if i >=400:
    temp=min(temp,dp[i-400])
  if i >=100:
    temp=min(temp,dp[i-100])
  if i >=50:
    temp=min(temp,dp[i-50])
  dp[i]=temp+1

print(dp)

Question Types

그리디 문제는 그 문제를 해결하기 위한 아이디어를 생각해내는 것이 중요하다. 정형화된 틀 없이 그 순간순간 할 수 있는 최고의 선택을 통한 최적의 해를 구하는 방식이니 다양한 문제 풀이를 통한 해당 능력을 함양해야 한다.