그리디 알고리즘

*이코테 with 파이썬 정리노트입니다.

그리디(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법

매 순간 가장 좋아보이는 것을 선택하며, 나중을 고려하지 않는다.
그렇기 때문에 최적의 해를 찾을 수 없을 가능성이 다분하다.

예제 ) 거스름돈

카운터에는 거스름돈을 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
단, 거슬러 줘야 할 돈 N은 항상 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)

📌 대부분 그리디 알고리즘 문제에서는 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야한다.

실전문제 ) 큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만들어라.
단, 배열의 특정한 인덱스에 해당하는 수가 연속적으로 K번을 초과하여 더해질 수 없다.
ex) [2, 4, 5, 4, 6] / M=8 / K=3 일 때, 6+6+6+5+6+6+6+5 = 46

답안 예시

n,m,k = map(int, input().split())
data = list(map(int, input().split())

data.sort()
first = data[n-1]
second = data[n-2]

#가장 큰 수가 더해지는 횟수 계산
count = int(m / (k+1)) * k
count += m % (k+1)

result = 0
result += (count) * first
result += (m-count) * second

print(result)

나의 답안

m,n,k = map(int, input().split())
num = list(map(int, input().split()))

num.sort(reverse = True)
result = 0
while(k<n):
    if n-k > 0:
        result += num[0]*k
        n -= k
    else:
        result += num[0]*n
    result += num[1]
    n -= 1

print(result)