그리디 알고리즘(Greedy)

Greedy 알고리즘은 매 단계에서 현재 상황에서 가장 최선이라고 생각되는 선택을 하는 방식으로 문제를 해결하는 알고리즘 기법이다.

특정 상황에만 사용되는 최적의 해를 구하는데 사용한다.

 

정의만 보았을 때는 무슨 말인지 잘 이해가 안 갈수 있다.

문제가 주어지면 어떻게 코드를 짜야지 가장 최고의 효율로 문제를 해결할 수 있는지 고민해야하는 문제다.

즉, 특정 알고리즘 공식이 있는게 아니라 각 문제 상황마다 다른 최적의 해를 직접 구상해내야 한다.

예시를 통해 알아보자

---

거스름돈 문제

---

[문제]

거스름돈으로 줄 금액이 주어졌을 때 동전의 개수가 최소가 되도록 동전을 조합하라.

단, 사용가능한 동전의 단위는 500원, 100원, 50원, 10원만 가능하다.

 

해당 문제에 대한 최적의 알고리즘을 구하기 위한 접근

1. 현재 상황에서 가장 큰 동전 단위부터 가능한 최대 개수만큼 사용한다.

2. 남은 금액을 다시 계산하여 같은 방식으로 반복한다.

3. 남은 금액이 0이 되면 종료한다.

 

[파이썬 예시]

def min_coins(change, coin_types):
    coin_types.sort(reverse=True)  # 동전 단위를 내림차순 정렬
    coin_count = 0
    result = {}

    for coin in coin_types:
        if change == 0:
            break
        count = change // coin  # 현재 동전으로 줄 수 있는 최대 개수
        change %= coin          # 남은 거스름돈 계산
        coin_count += count     # 동전 개수 누적
        if count > 0:
            result[coin] = count

    return coin_count, result

 

Greedy 알고리즘이 위의 상황에서 사용가능한 이유는 동전의 단위가 배수 관계에 있기 때문이다.

만약 동전의 단위가 400원, 300원 처럼 배수관계가 보장되지 않으면 

Dynamic programing 이나 Brute Force를 사용해야 한다.

 

Greedy 동전문제 예시: https://www.acmicpc.net/problem/11047

Dp 동전문제 예시: https://www.acmicpc.net/problem/2294

 

---

 

문제 조건을 보면 알겠지만 Greedy동전문제는 동전들이 배수관계가 있음이 보장되고

Dp는 보장되지 않는다.

따라서 Greedy는 동전이 배수관계가 있는 것처럼

특정한 상황일때만 사용할 수 있는 효율적인 알고리즘을 본인이 직접 구현하는 것이다.

 

한마디로... 생각을 많이 해봐야하고 경험이 중요하다...

알고리즘 특성상 특정 알고리즘을 사용해서 바로 푸는 문제들이 아니기 때문에

ICPC, UCPC, codeforce 등 경쟁적 프로그래밍에서 많이 출제되는 유형이다.

 

그리디를 사용해야 하는지 동적 계획법(or 완전 탐색)을 사용해야 하는지 구분하는 방법은 시간복잡도에 있다.

그리디는 해당 문제의 최적화된 알고리즘이기에 보통 O(n)으로 해결하는 문제가 많이 등장한다.

입력값들의 범위가 10만을 넘어가고 등으로 눈치챌 수 있다.

 

반면에 동적계획법이나 완전탐색은 모든 경우의 수를 다 탐색해보아야 하기 때문에 입력값들의 범위가 크지 않다.

보통 값들의 범위가 1000단위(10000만 되도 1초안에 O(n2)이 빠듯하기 때문에)이다.

*물론 제한시간이 크면 더 늘어날 수도 있음

 

아무쪼록 많이 풀어봐서 경험을 늘리거나 선천적으로 명석하거나... 등이 그리디를 잘할 수 있는 법이다.