[알고리즘] 그리디 알고리즘

1. 탐욕(Greedy) 이란?

그리디 알고리즘은 문제 해결 과정에서 결정하는 순간마다 눈 앞에 보이는 최선의 선택을 하는 알고리즘을 뜻한다. 즉 해결 과정 전체, 혹은 미래의 상황을 고려하지 않고 당장의 순간에 최선의 선택을 고려하는 알고리즘이다.

• 다른 알고리즘에 비해 구현하기가 쉬움
• 실행 속도가 빠름
• 특정한 상황에서만 적용 가능.

그리디는 위에서 설명했듯이 모든 순간에 적용 가능한 알고리즘은 아니다. 그리디 알고리즘을 사용할 수 있는 특정한 상황은 다음과 같다.

• 최적 부분 구조 : 순간마다의 부분 최적해들의 합이 곧 전체 문제의 해답과 동일할 때만 사용 가능.
• 그리디 선택 속성 : 이전의 선택이 이후의 선택에 영향을 끼치지 않음.

---

2. 대표 예시

그리디의 대표적인 예시는 거스름돈 문제다. 다음 설명을 기반으로 이해해보자.

문제

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

해결법

이 문제의 해결 과정에 제일 중요한 건 2가지다. 아래의 조건을 만족해야만 최적의 해를 구할 수 있다.

• 가장 큰 단위의 동전을 기준으로 나눠주며 작은 동전으로 나아간다.
• 동전의 금액은 항상 작은 동전의 배수여야 한다.

def greedy_change(amount):
  coins = [500, 100, 50, 10, 1]
  result = []

  for coin in coins:
    result.append(amount // coin)
    amount %= coin

  return result

amount = 1260
print(greedy_change(amount))

---

동전 예시가 대표적이지만 그리디는 실제로 다른 알고리즘의 문제 해결에도 많이 사용된다. 대표적이면서 중요한 예시만 몇 개 나열하면 다음과 같다.

• 하프닝 알고리즘 : 주어진 숫자들을 두 그룹으로 나누어 그 합이 최대한 가까워지도록 하는 알고리즘
• 최소 신장 트리(MST) : 그래프의 모든 정점을 연결하는 트리 중에서 가중치의 합이 최소인 트리
• 다익스트라 알고리즘 : 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는 알고리즘
• 프림 알고리즘 : 최소 신장 트리를 찾는 알고리즘 중 하나

지금은 아니지만 추후에 시간이 된다면 각각의 알고리즘에 대해서 알아봐야겠다.