그리디 알고리즘 (Greedy Algorithm)

 

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

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

 

ex) 거스름돈 문제 - 가장 큰 화폐 단위부터 돈을 거슬러 줌

         ㄴ 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위들을 종합해 다른 해가 나올 수 없다!

n = int(input())
cnt = 0
coin = [500, 100, 50, 10]

for i in coin:	# 시간 복잡도 O(K) <- 동전의 종류 K개
    cnt += n // i
    n %= i

print(cnt)

 

실전 문제1. 큰 수의 법칙

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

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

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

    if m == 0:
        break

    res += second
    m -= 1

print(res)

- 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다.

- 가장 큰 수 K번 + 두 번째로 큰 수 1번 반복

* M의 크기가 커질 경우 시간 초과 판정. 다른 방법으로 문제를 해결해보자.

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

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

cnt = m // (k + 1) * k + m % (k + 1)    # 가장 큰 수 더하는 횟수
res += cnt * first + (m - cnt) * second # 더하기

print(res)

두 번째 알고리즘 규칙

 

실전 문제2. 숫자 카드 게임

n, m = map(int, input().split())
res = 0

for i in range(n):
        cards = list(map(int, input().split()))
        if res < min(cards):
                res = min(cards)

print(res)

- 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는다.

 

실전 문제3. 1이 될 때까지

n, k = map(int, input().split())
cnt = 0

while n != 1:
    if n % k == 0:
        n //= k
    else:
        n -= 1
    cnt += 1

print(cnt)

- 최대한 많이 나누기를 수행하면 된다.