✏️ 그리디 알고리즘(Greedy Algorithm)이란?
그리디 알고리즘이란 현재 시점에서 최적의 선택을 하는 알고리즘 설계 기법이다. 해석 그대로 탐욕 알고리즘 또는 탐욕법이라고 불린다.
그림에서 보듯이 그리디 알고리즘은 지금 당장 좋은 것만 고르는 방법으로, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.
그리디 알고리즘이 최적의 선택을 나타내진 않는다.
📌 그리디 알고리즘 예시 문제: 거스름돈
백준 5585번: 거스름돈 (https://www.acmicpc.net/problem/5585)
: 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
문제 해설
: '거스름돈 개수가 가장 적게 잔돈을 준다.'는 말은 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다. 가장 먼저 500엔으로 가능한만큼 거슬러 주고, 그 다음 100엔, 50엔, 10엔, 5엔, 1엔 차례대로 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.
예를 들어, 지불할 금액이 380엔이라고 하자.
타로가 1000엔을 냈으므로 거슬러 주어야 할 돈은 1000엔-380엔인 620엔이다.
가장 적은 잔돈의 개수는 500엔 1개, 100엔 1개, 10엔 2개로 총 4개가 답이 된다.
python으로 알고리즘을 구현해보면 다음과 같다.
def greedy(n):
cnt = 0
money = 1000 - n
coin = [500, 100, 50, 10, 5, 1]
for i in coin:
cnt += money//i
money %= i
return cnt
📌 그리디 알고리즘 예시 문제: 큰 수의 법칙
2019 국가 교육기관 코딩테스트: 이것이 코딩테스트다 p92
동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.
예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 +6 +5인 46이 된다.
입력조건
-
첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
-
둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
-
입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력조건
- 첫째줄에 동빈이의 큰 수의 법칙에 따른 답을 출력한다.
문제해설
이 문제는 일단 입력값 중에 가장 큰 수와 두 번째로 큰 수만 저장하면 된다. 연속으로 더할 수 있는 횟수는 최대 K번이므로 '가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산'을 반복하면 된다.
python으로 알고리즘을 구현해보면 다음과 같다.
n, m, k = map(int, input().split()
data = list(map(int, imput().split())
data.sort() # 입력받은 수 정렬
first = data[n-1] # 가장 큰 수
second = data[n-2] # 두 번째로 큰 수
result = 0
while True:
for i in range(k): # 가장 큰 수를 k번 더하기
if m == 0 : # m이 0이라면 반복문 탈출
break
result += first
m -= 1 # 더할 때마다 횟수 m-1 차감
if m == 0: # m이 0이라면 반복문 탈출
break
result += second # 두 번째로 큰 수를 한 번 더하기
m -= 1 # 더할 때마다 횟수 m-1 차감
print(result)
이 외에도 수열로 문제를 풀 수 있다. 해당 방법은 <이것이 코딩테스트다 p95>를 참고하자.
📌 그리디 알고리즘 예시 문제: 숫자 카드 게임
2019 국가 교육기관 코딩테스트: 이것이 코딩테스트다 p96
숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.
단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
-
숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며 M은 열의 개수를 의미한다.
-
먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
-
그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
-
처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자를 뽑을 수 있도록 전략을 세워야 한다.
입력조건
-
첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 ≤ N, M ≤ 100)
-
둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000이하의 자연수이다.
출력조건
- 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.
문제해설
이 문제는 "각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수"를 찾는 것이 문제의 핵심이다.
python으로 알고리즘을 구현해보면 다음과 같다.
n, m = map(int, imput().split()
result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
data = list(map(int, input().split())
# 현재 줄에서 '가장 작은 수' 찾기
min_value = min(data)
# '가장 작은 수'들 중에서 '가장 큰 수' 찾기
result = max(result, min_value)
print(result)
📃 참고문헌
<이것이 코딩테스트다 p86~102>
https://www.acmicpc.net/problem/5585
