그리디 알고리즘 (Greedy Algorithm) , 탐욕

그리디 알고리즘(Greedy Algorithm)

 

그리디 알고리즘은 "매 선택에서 당장 좋은것만을 선택해 나가는 방법"을 뜻한다. 특정 기준에 따라서 좋은 것을 선택해야하는 알고리즘이기 때문에 문제에서 어느정도 제시해준다. 그리고 좋다, 나쁘다의 기준을 세워야하기 때문에 정렬 알고리즘과 섞여서 나오는 문제들이 많다.

 

간단한 예제 (거스름 돈)

 

그리디 알고리즘을 대표하는 문제로 '거스름 돈' 문제가 있다.

자판기에 거스름돈을 배출해야 하는데 , 자판기에는 500, 100, 50, 10원짜리가 무수히 존재한다. 이때 거슬러줄 최소 동전의 개수를 구하라. (단, 거스름 돈은 항상 10의 배수이다.)

이러한 문제가 있다면, 무조건 큰 단위의 동전(500원)으로 최대한 거슬러주고, 그 다음 가능한 큰 단위의 동전(100원)을 선택하는 방식으로 해결이 가능하다.

위의 예제와 같은 경우는 거스름 돈이 항상 10의 배수이기 때문에, 그리디 알고리즘을 적용해도 빗나갈 일이 없다. 그래서 그리디 알고리즘에 매우 효과적이지만, 다른 문제에 그리디알고리즘을 적용시킬때는 이 방법이 정당한지, 예외는 없는지 반드시 확인해야한다.

다시 말하면, 매 선택의 순간에 대해서는 최적이지만, 종합적으로 고려하면 최적이라는 보장은 없다.

 

 

그리디 알고리즘 문제 목록(백준)

 

14916 번 : 거스름돈 (난이도 : 실버5)

https://www.acmicpc.net/problem/14916

거스름돈

n = int(input())
five = n // 5
two = 0
while (n > 0) :
    if ((n - (five * 5)) % 2 == 0):
        two = (n - (five * 5)) // 2
        answer = five + two
        break
    else : 
        five -= 1
        if five <= 0 :
            answer = -1
            break

print(answer)

 

2217번 : 로프 (난이도 : 실버4)

https://www.acmicpc.net/problem/2217

로프

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
arr.sort(reverse=True)
solution=[]
for i in range(len(arr)):
    solution.append(arr[i] * (i+1))
print(max(solution))