Kyoungtae Min

진화하는 엔지니어가 되기 위한, 공부 내용 정리 및 기록

3 분 소요

그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 개념

그리디 알고리즘은 탐욕법이라고도 말한다. ‘Greedy’라는 영단어 자체가 ‘탐욕스러운’이라는 뜻을 가지고 있어서 탐욕 알고리즘이라고도 불린다. 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 즉, 해당 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있어야 문제가 풀리도록 출제되는 경우가 많다.

그리디 해법은 정당성 분석이 매우 중요하다. 단순히 현재 상황에서 가장 좋아 보이는 것을 반복적으로 선택하는 것 만으로도 최적의 해를 보장할 수 있는지를 검토하는 과정이 꼭 필요하다.

[문제] 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.

위와 같은 그림과 상황이 주어졌다.

  • Q. 최적의 해는 무엇인가? 라는 문제가 나왔을 때의 답은 간단하다. 99라는 큰 수로 이어지는 (7, 3, 99)이다.
  • Q. 단순히 매 상황에서 가장 큰 값만 고른다면? 라는 문제가 나왔을 때의 답은 달라진다. 매 상황마다 가장 큰 값만 선택하는 것을 반복하게된다. 따라서 답은 (7, 12, 6)이다.

그리디 알고리즘은 이처럼 매 상황에서 가장 큰 값만 고르는 방식이라고 말할 수 있다.

따라서, 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 그렇기 때문에, 실제로 다양한 프로그램을 개발할 때에는 그리디 알고리즘을 사용하여도 충분히 최적의 해에 가까운 값을 얻을 수 있거나, 최적의 해를 얻을 수 있을 때 사용하는 경우가 많다.

다만, 코딩 테스트에서는 어떠한 입력이 주어졌을 때 어떠한 출력값이 나와야 한다는 것을 미리 출제자가 정해놓고 문제를 만드는 경우가 많기 때문에 그리디 알고리즘 문제가 출제가 된다면 그리디 알고리즘으로 얻은 값이 최적의 해가 되는 상황에서, 단순히 그리디 알고리즘을 이용해도 최적의 해를 얻을 수 있다는 것을 추론할 수 있어야 문제가 풀리도록 출제하는 경우가 많다.

[예제]

좀 더 이해하기 위해서 그리디 알고리즘의 가장 대표적인 예제인 거스름돈 문제를 풀어보자. —

거스름 돈: 문제 설명

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

거스름 돈: 문제 해결 아이디어

  • 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
  • N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 된다.

N = 1260 이라면,

1,260원이 0원이 될 때까지 거슬러주면 된다. 먼저 500원에 대해서 거슬러주게 되면 500원짜리 두 개를 거슬러 줄 수 있다.(1260 - 1000 = 260) 다음은 100원짜리를 두 개 거슬러주고(260 - 200 = 60), 그 다음 50원짜리 한 개(60 - 50 = 10), 마지막으로 10원짜리 한 개를 거슬러주면 된다(10 - 10 = 0). 결과적으로 총 6개의 동전으로 1,260원을 거슬러 줄 수 있다.

이렇게 단순히 가장 큰 화폐부터 거슬러주는 것으로 최적의 해를 보장 할 수 있는 이유는 무엇일까? 정당성 분석을 통해 알아보자.

거스름 돈: 정당성 분석

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

만약에 800원을 거슬러 주어야 하는데 화페 단위가 500원, 400원, 100원이라면 어떻게 될까?

그리디 알고리즘에 따르면 500원짜리 1개와 100원짜리 3개를 거슬러주게 되어 4라는 답이 나오게 된다. 그러나 최적의 해는 400원짜리 두 개인 2이다. 즉, 큰 단위가 작은 단위의 배수가 아니라면 이와 같은 알고리즘을 이용한 최적의 해를 보장할 수가 없는 것이다.

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

예를 들어, 이런 문제를 처음 만났을 때 굉장히 다양한 해법이 나올 수 있을 것이다. 그냥 10원짜리로만 거슬러준다거나, 랜덤으로 한 개씩 뽑아서 거슬러주는 것과 같이 다양한 방법으로 거슬러 줄 수 있다는 것을 생각해 내고 그렇게 고민하다가 직관적으로 ‘그냥 가장 큰 단위부터 거슬러주게 되면 최소한의 개수로 거슬러 줄 수 있지 않을까?’하는 생각을 떠올리게 되고, 그렇게 했을 때에도 최적의 해를 항상 보장할 수 있는지 고민해 보는 것이 중요하다.

본 예제에서는 500원, 100원, 50원, 10원 형태로 항상 큰 단위가 작은 단위의 배수라는 것을 이해하고 그렇기 때문에 단순히 큰 단위부터 거슬러주게 되면 문제를 해결할 수 있다는 것을 떠올릴 수 있는 과정이 중요하다.

거스름 돈: 답안 예시 (Python)

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

6

거스름 돈: 시간 복잡도 분석

  • 화폐의 종류가 K라고 할 때, 위 소스코드의 시간 복잡도는 O(K)이다. 즉, 화폐의 종류만큼만 반복을 수행하면 답을 도출할 수 있다.
  • 따라서 이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.

오늘은 그리디 알고리즘에 대해서 알아보았다. 이제 문제를 직접 해결해 보면서 내 것으로 만들어야지. 데이터 분석, 머신러닝, 딥러닝 관련 공부만 하다가 알고리즘 공부를 하기 위해 처음 시작했는데 이건 이거대로 재미가 있어서 다행이다. 중간에 그만두지 말고 끝까지 해보자 파이팅.

본 포스팅은 [안경잡이개발자]나동빈님의 유튜브강의를 기반으로 작성하였습니다. 좋은 강의를 올려주신 동빈님께 감사합니다. 더 자세히 알고 싶은 분은 링크를 타고 가서 보시기 바랍니다.

참고