greedy

 

그리디 알고리즘 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'

 

그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘 문제 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘으로 분류되고 암기가 필요하지만 이런 특이 케이스를 제외하고 문제를 풀기 위한 최소한의 아이디어(현재 상황에서 가장 좋아 보이는 것만을 선택)를 요구한다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시하고 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

그리디 알고리즘의 정당성

코딩 테스트 문제를 만났을 때 바로 문제 유형을 파악하기 어려우면 그리디 알고리즘을 의심하고 그리드 알고리즘으로 안되면 다이나믹 프로그래밍 -> 그래프 알고리즘

 

---

거스름돈

그리디 알고리즘 유형인 이유 :  '가장 큰 순서대로' '가장 큰 화폐 단위부터' 큰 단위가 항상 작은 단위의 배수 형태이므로 

# N원을 최대한 큰 동전이 많도록
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)이다.

'''
N = int(input('10의 배수인 거스름돈'))

for coin in coin_types:
    if N//coin > 0:
        count += N//coin
        N %= coin

print(count)

if N//500 > 0:
    coin1=N//500
    m1=N-500*coin1
    if m1//100 > 0:
        coin2=m1//100
        m2=m1-100*coin2
        if m2//50 > 0:
            coin3=m2//50
            m3=m2-50*coin3
            if m3//10 > 0:
                coin4=m3//10
                print(coin1+coin2+coin3+coin4)
'''

 

큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

'''
1. list로 nmk 를 받는다
2. list[n] = input() 배열을 받는다
가장 큰수를 k번 더하고 두번째큰수를 1번더하고 가장큰수를 k번더하기를 반복한다
단, m-2 // k = 몫은 두번째 수 개수 = a (???)
m-a = 가장 큰수의 개수 
'''

# 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] # 두 번째로 큰 수
a = m//k # k의개수
b = m-a
first*b+second*a

 

출처 : 이것이 취업을 위한 코딩 테스트다 with 파이썬