[알고리즘] Greedy (탐욕법) - (1)

Greedy (탐욕법)

1. 탐욕법 (Greedy)

• 탐욕 : 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘
  -> 매 순간 가장 좋아 보이는 것 을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
  예외) 다익스트라 알고리즘 - 암기가 필요

• 그리디 알고리즘의 경우 많은 유형을 접해보고 문제를 풀어보며 훈련해야함
  => 창의력 즉, 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함
  => 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 출 수 있는지를 파악할 수 있어야 함

• 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘임
  => 문제에서 가장 큰 순서대로 혹은 가장 작은 순서대로 와 같은 기준을 알게 모르게 제시해 줌

  이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됨

2. Greedy 알고리즘의 정당성

그리디 알고리즘이 모든 알고리즘에 적용될 수 는 없다.

대부분의 문제는 그리디 알고리즘을 사용했을 때, 최적의 해를 못찾을 가능성이 존재한다.

하지만 '가장 큰 화폐 단위부터 돈을 거슬러 줌' 과 같이 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있으면 매우 효과적이고 직관적이다.

따라서 그리디 알고리즘으로 문제의 해결법을 찾았을 때는 해법이 정당한지 검토 해봐야 한다.

예를들어 거스름돈 문제가 그리디로 해결 가능 한 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

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

어떤 코딩 테스트 문제를 만났을 때, 문제 유형을 바로 파악하기 어려우면 그리디 알고리즘을 의심해보고, 문제를 해결할 수 있는 방법이 존재하는지 고민하고 안된다면 다른 알고리즘으로 고민해 본다.

문제를 처음봤을 때 고민해 봐야 할 것은 이것 저것의 다양한 아이디어이다.

예를 들어 다시 거스름돈 문제로 돌아와 보자.

1. '가장 먼저 10원짜리로 거슬러 주면 어떻게 될 지' 생각해 보고 그렇게 되면 최적의 해를 못구한다고 문제점을 인식한다.
2. 또 다른 가능한 풀이법을 생각해 본다, 그럼 가장 큰 액수부터 거슬러 주면 어떻게 될까?

=> 거스름돈 문제에서 큰 단위가 작은 단위의 배수니까 이렇게 하면 항상 최적의 해를 보장할 수 있다는 생각까지 하면 된다.

실제 거스름돈 문제에서 큰 단위가 작은 단위의 배수가 아니라면 greedy 알고리즘을 사용할 수 없다.

화폐의 단위가 무작위 인 경우 DP(다이나믹 프로그래밍)으로 해결해야한다.

EX1) 거스름돈

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

📝 풀이

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제 => 간단한 아이디어만 떠올릴 수 있으면 문제 해결 가능하다.

가장 큰 화폐 단위부터 돈을 거슬러 주는 것 이 바로 그 아이디어이다.

N원을 거슬러 줘야할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 주고, 그 다음 100원, 50원, 10월짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

📚 예시

0. 초기 단계 - 남은 돈 : 1260원

   화폐 단위	500원	100원	50원	10원
   손님이 받은 개수	0	0	0	0

1. 남은 돈 : 260원
   1260원에서 500원으로 거슬러 줄 수 있는 돈은 500원짜리 2개로 1000원, 그러면 260원이 남는다.

   화폐 단위	500원	100원	50원	10원
   손님이 받은 개수	2	0	0	0

2. 남은 돈 : 60원
   260원에서 100원으로 거슬러 줄 수 있는 돈은 100원 짜리 2개로 200원, 그러면 60원이 남는다.

   화폐 단위	500원	100원	50원	10원
   손님이 받은 개수	2	2	0	0

3. 남는 돈 : 10원
   60원에서 50원으로 거슬러 줄 수 있는 돈은 50원 짜리 1개로 50원, 그러면 10원이 남는다.

   화폐 단위	500원	100원	50원	10원
   손님이 받은 개수	2	2	1	0

4. 남는 돈 : 0원
   10원에서 10원으로 거슬러 줄 수 있는 돈은 10원 짜리 1개로 10원, 그러면 다 거슬러 줬다.

   화폐 단위	500원	100원	50원	10원
   손님이 받은 개수	2	2	1	1

따라서 손님이 받을 거스름돈의 개수는 500원 2개, 100원 2개, 50원 1개, 10원 1개로 총 6개 이다.

⌨코드

n = 1260
count = 0

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

for coin in coin_types:
    count += n // coin
    n %= coin

print(coin)

코드를 보면 화폐의 종류만큼 반복을 수행하는 것을 볼 수 있다.

화폐의 종류를 N개라고 한다면 이 코드의 시간복잡도는 O(N) 이다.
=> 이 알고리즘은 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.