해당 시리즈는 이것이 코딩 테스트다 라는 책의 내용을 기반으로 작성된 글이며 알고리즘의 기본 개념이 되는 방법론들의 기본 개념을 학습하고 포스팅 할 예정입니다. 모든 소스 코드는 여기서 확인하실 수 있습니다.

그리디 알고리즘 - 탐욕법

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다. — 나무위키

정의

그리디 알고리즘이란 나무위키에서 언급한 것 처럼 현재의 상황에서 가장 최적의 답을 도출하는 알고리즘이다. Greedy라는 단어는 우리말로 탐욕적인 이라고 해석되기 때문에, 탐욕법이라고도 불린다.

정의 자체로 충분히 이해가 되겠지만 조금 다르게 다시 얘기해보자면, 가장 이득을 볼 수 있는(탐욕적인) 조건을 유추하여, 최대의 이득을 보기 위해 알고리즘이라고 할 수 있다. 아래의 예제를 보며 확인해보자.

문제

그리디 알고리즘의 대표적인 예시로는 거스름돈 예제가 있다. 문제는 아래와 같다.

• 당신은 음식점에서 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전을 무한히 가지고 있다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

위 문제에 아래의 문장을 추가하면, 왜 탐욕법 이라고 불리는지 이해하기 쉬울 것이다.

• 모든 동전의 가격이 하나당 10억원이라서, 당신은 최소한의 동전만을 주고 최대한 많은 동전을 소유하고자 한다.

해결

해당 문제는 최대한 큰 단위의 동전을 많이 줘야 한다 라는 간단한 법칙만 발견한다면 쉽게 풀 수 있다. 파이썬을 이용한 풀이법은 아래와 같다.

def coin_count(value):
    coins = [500, 100, 50, 10]
    count = 0

    for coin in coins:
        count += value // coin #가장 단위가 큰 코인부터 최대로 많이 준다.
        value = value % coin

    return count

print(coin_count(1260))

주의점

그리디 알고리즘을 풀 때 주의할 점은, 현재의 상황에 가장 적합한 답을 도출하는 알고리즘이다. 그렇다면 문제를 풀 때 사용한 조건 또는 알고리즘이 가장 적합하다는 것에 대한 확신이 존재해야 한다. 위 문제에서 해당 방법이 가장 적합한 이유는 아래와 같다.

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

흐름

그리디 알고리즘을 풀 때는 아래와 같은 흐름을 가지고 푸는 것이 개인적으로 좋아 보인다.

• 문제의 답을 도출하는 가장 적절한 알고리즘을 생각한다.
• 해당 알고리즘이 가장 적절할 수 밖에 없는 이유를 생각한다.
• 소스 코드를 작성한다.

알게된 팁

파이썬은 1초에 대략 2000만번의 연산이 가능하다. 즉 다양한 시간 복잡도(O(n), O(n2), O(NlogN))등에서 N에 연산하게 될 데이터의 양을 넣었을 때 2천만번이 넘어간다면, 1초를 넘는다고 간주해도 된다. 이를 통해 해당 문제에서 주어진 시간과, 데이터의 양을 토대로 시간 복잡도를 통과할 수 있을지 유추할 수 있다.