[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm)

탐욕법으로도 알려진 문제 해결 방법이다. 

이름 그대로 주어진 문제를 단순하게 탐욕적으로 푸는 알고리즘이다.

탐욕적이라는 말은 '현재 상황에서 가장 좋은 것만 계속 고르는 방법'을 말한다.

 

그리디 방법음 알고리즘의 각 단계에서 그 순간에 최적이라고 생각하는 것을 선택한다.

또한 그리디로 문제를 해결할때는 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 사용할 수 있다.

 

우리는 그리드 문제를 풀 때는 다익스트라(dijkstra) 또는 위상 정렬(topological sort) 알고리즘처럼 특정 알고리즘 코드를 미리 알 필요는 없다. 대신 우리는 문제를 봤을 때 '그 문제가 그리드 알고리즘으로 해결할 수 있는지'에 대해 알아야 한다. 그럼 어떻게 알 수 있을까?

 

---

 

 다양한 그리드 알고리즘 유형의 문제를 풀어봐야 한다. 수학 문제를 풀듯, 핵심 키워드나 조건을 보고 어떤 유형인지 알아야 한다. 만약 어떤 문제를 보았을 때, 문제 유형을 잘 모르겠으면 그리드 알고리즘을 생각해 보고, 탐욕적인 방법으로 접근 가능한지 고민해보면 좋다.

 

 탐욕적인 방법으로 문제를 접근했을 때, 모든 case에 적용가능한지 생각해봐야한다. 항상 최적의 해를 보장할 수 있는지 고민해봐야 한다. 그리드 알고리즘으로 해결 방법을 찾을 수 없다면, 다이내믹 프로그래밍이나 그래프 알고리즘으로도 가능한지 다시 고민해 보자. 

 

---

예제) BOJ 11047 - 동전 0

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

11047번: 동전 0

 

N, K = map(int, input().split())

Coins = []
count = 0

for _ in range(N):
    Coins.append(int(input()))

for i in range(N - 1, -1, -1):
    if K - Coins[i] >= 0:
        count += K // Coins[i]
        K %= Coins[i]

print(count)

그리드 알고리즘을 사용하는 대표적인 문제. 아이디어만 떠올리면 간단하게 해결할 수 있다.

화폐를 생각하면 쉽게 떠올릴 수 있다. 동전의 개수를 최소화하려면 동전의 값이 큰 순서대로 빼보면 된다.

예를 들어 700원을 생각하면 700원을 넘지 않는 가장 큰 값 500원을 빼주고, 남은 200원은 200원을 넘지않는 가장 큰 값 100원 두 개를 빼주면 된다. 따라서 매번 선택할 때마다 가장 큰 금액을 고르면 동전 개수를 최소화할 수 있다.

또한 조건에서 동전의 값들이 배수관계인 것도 힌트가 될 수 있다.