그리디 알고리즘

1. 개요

Greedy(탐욕)이라는 이름에서 알 수 있듯이, 미래의 영향을 고려하지 않고 지금 당장 좋은 것만 고르는 방법이다.

2. 사용예시

초등학교 수학문제로 본 적 있는 거스름돈의 예시가 가장 대표적인 그리디 알고리즘이다.

 카운터의 종업원이 1000원, 500원, 100원, 50원, 10원이 무한히 있다고 할 때, 
 종업원이 최소한의 개수로 거스름 돈을 주는 경우를 구하세요

위와 같은 문제가 있다면 이는 그리디 알고리즘으로 풀 수 있다. 왜냐하면 가능한 최대한 큰 화폐로 거슬러 주는 것이 최적의 해를 구하는 방법이기 때문이다.

3. 사용조건

앞서 지금 당장 좋은 것만 고르는 방법이다 라고 그리디 알고리즘을 설명하였다. 그럼 이 그리디 알고리즘의 사용조건은 무엇일까?

당연하게도 지금 당장 좋은 것만 골라도 정답일까? 에 대해 고민해야 한다. 이를 그리디 알고리즘의 정당성이라고 하자.

그렇다면 위의 동전 문제에서의 정당성을 확인해 보자.

 1000원 단위로 거슬러 줄 수만 있다면 500원 2개, 100원 10개 보다 항상 최적의 해일 것이다. 
 즉, 현재 1000원 단위로 최대한 거슬러 주는게 미래의 상황에서도 가장 좋은 상황인 것이다. 

이와 같이 그리디 알고리즘에서 문제 풀이를 위해 정당한 검증이 있어야한다.

4. 코테 에서의 그리디 알고리즘

1️⃣ 문제 해결 방안이 바로 떠오르지 않으면 그리디 알고리즘 떠올리기.

2️⃣ 문제 풀이를 위한 간단한 가설(현재 가장 좋아보이는 방법을 선택)을 세우고 맞는지 검증한다.

3️⃣ 구현

5. 그리디 알고리즘의 예

1. 모험가 길드

모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로
구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.
N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하라
입력 예
- 입력: 5 2 3 1 2 2
- 출력: 2

풀이

풀이 1 (잘못된 풀이)

import sys  
from collections import deque  
N = int(sys.stdin.readline())  
  
player = list(map(int, sys.stdin.readline().split()))  
player.sort(reverse=True)  
player_deq = deque(player)  
ans = 0  
while player_deq:  
    num = player_deq.popleft()  
    ans += 1  
  for _ in range(num):  
        if player_deq:  
            player_deq.popleft()  
        else:  
            break  
print(ans)

플레이어를 내림차순으로 정렬하고 공포도가 큰사람을 최대한 포함시켜 그룹수를 낮추려함

모험가가 마을에 남아도 되는 부분을 생각하지 않은 풀이로 2명의 모험가의 공포도가 3 1 과 같은 경우 오류 발생

풀이 2 (답안 풀이)

import sys  
from collections import deque  
N = int(sys.stdin.readline())  
players = list(map(int, sys.stdin.readline().split()))  
players.sort()  
  
groups = 0  
group_players = 0 
  
for player in players:  
    group_players += 1  
  if group_players >= player:  
        groups += 1  
  group_players = 0  
  
print(groups)

최대한 많은 그룹을 만드는 것이 목표이기 때문에 공포도를 낮은 순서로 정렬하여 최소한의 그룹 결성 조건(현재 그룹의 공포도 >= 그룹 맴버수)를 만족하면 바로 그룹을 형성하는 방식으로 문제 풀이를 진행하였다.

이 때 공포도가 가장 낮을 수록 그룹의 수가 많아지므로 그리디 알고리즘을 적용하였다.

Reference

이것이 취업을 위한 코딩테스트다 with 파이썬

그리디 알고리즘 (Greedy algorithm)