[코테] 그리디 알고리즘

📚그리디 알고리즘  

 주어진 문제를 단순하고 탐욕적으로 푸는 알고리즘. 탐욕적 이라는 것은 현재 상황에서 지금 당장 좋은 것만을 고르는 것을 의미한다. 대표적으로 가장 큰 화폐 단위부터 돈을 거슬러 주는 문제가 있다. 

 

✔ 문제 

 손님이 돈 N원을 지불하였을 때, 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)이다. 

 

 그리디 알고리즘을 사용하기 위해서는 그 해법이 정당한지를 검토해야 한다. 위 문제의 경우 반환하는 큰 동전의 단위가 항상 작은 단위의 배수이므로, 작은 단위 동전을 조합해서 다른 해가 나올 수 없기 때문에 정당하다고 볼 수 있다. 

 만약 800원을 거슬러 줘야하고 동전이 500원/400원/100원 인 상황이라면 2개의 동전(400원 2개)를 거슬러 줘야 하지만, 그리디 알고리즘으로는 500 + 100 + 100 + 100 원을 거슬러 줘야 한다. 

 

 

✅ 3-2. 큰 수의 법칙  (p.92) 

주어진 배열이 있을 때, 배열의 수를 M번 더하여 가장 큰 수를 만들기. 단 배열의 특정한 인덱스에 해당하는 수가 연속해서 K 번을 초과하여 더해질 수 없다. 배열의 크기는 N. 

#N/M/K를 공백으로 구분해서 입력받기 
n,m,k = map(int, input().split())
#N개의 수를 공백으로 구분하여 입력
data = list(map(int, input().split()))

data.sort()

first = data[n-1]
second = data[n-2]

result = 0

while True:
  for i in range(k):
    if m == 0:
      break
    result += first 
    m -= 1

  if m == 0:
    break

  result += second 
  m -= 1 

print(result)

 문제를 구체적+단순화 할 수 있어야 함. 위의 문제를 단순화하면 입력값 중에서 가장 큰 수와 두 번째로 큰 수를 우선 저장하고, 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다. 

 

 

 

📚 Reference 

• 나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬, 한빛미디어, 2020