Greedy(그리디 알고리즘)

Greedy 알고리즘

말 그대로, 어떠한 문제에 대해 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
탐욕적? (= 현재 상황에서 지금 당장 좋은 것만 고르는 방법)
매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음

사전 지식 없이도 풀 수 있는 유형의 문제이지만, 그 만큼 많은 유형을 접해보고 문제를 풀어보아야 함!

창의력, 문제를 풀기 위한 아이디어를 떠올릴 수 있는 능력이 중요함!

큰 수의 법칙

다양한 수로 이뤄진 배열이 있을때, 배열의 크기 N, 숫자가 더해지는 횟수 M, K가 주어질때, 주어지는 수들을 M번 더하여 가장 큰수를 찾아내고, 이때 같은 수가 연속해서 K번을 초과하여 더해질 수 없는 조건

반복되는 수열에 대해 파악하는 것이 가장 중요함!

# 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] # 두 번째로 큰 수

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

result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기

print(result) # 최종 답안 출력

Greedy 알고리즘의 정당성

모든 알고리즘 문제에 적용할 수 있는 것은 X
대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 높지만, 거스름돈 문제에서 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제에 접근 했을때, 정확한 답을 찾는다는 보장이 있을 때는 매우 효과적이고 직관적임!

따라서, 대부분의 그리디 알고리즘 문제에서는 문제풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 함!