[01] 그리디 (greedy) 알고리즘

그리디 알고리즘이란 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 문제 해결 알고리즘이다.

즉, 바로 눈 앞의 이익만을 좇는 알고리즘이다.

 

대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다.

어떠한 문제가 있을 때, 단순 무식하게 지금 당장 좋은 것을 고리는 방법이다.

 

매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

* 탐욕 선택 속성 : 앞의 선택이 이후 선택에 영향을 주지 않는 것

 

 

그리디 알고리즘의 대표 문제들

 

1. 거스름돈 문제

당신은 음식점의 계산을 도와주는 점원이다.

카운터에는 거스름 돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다.

손님에게 거슬러줘야 할 돈이 N원이라면,

거슬러 줘야 하는 동전의 최소 개수는?

(단, N은 항상 10의 배수이다.)

 

 

이 문제에 접근하는 방법은 '가장 큰 화폐 단위부터' 돈을 거슬러주기 이다.

즉, 500원, 100원, 50원, 10원의 순서대로 거슬러 최소의 동전 개수로 계산하는 것이다.

 

이러한 방식으로 문제를 해결해보면, 만약 n이 1260원일 경우,

# n이 1620일 경우

n = 1260
count = 0

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

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

 

그리디 알고리즘의 정당성

그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 없다.

하지만 특정한 문제에 접근했을 때 정확한 답을 찾을 수 있을 때 매우 효과적이고, 직관적이다.

 

그리디 알고리즘으로 정답을 찾은 경우, 해법이 정당한지 검토하는 과정이 중요하다.

예로, 거스름돈 문제에서 해법이 정당한지 쉽게 검토하는 방법은

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

 

만약 문제를 처음 만나게 된다면, 차근차근 작은 수 부터 생각하면서, 방법을 거슬러 올라가서 생각하는 방식이 필요하다.

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

 

 

2. 큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.

단, 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

 

만약, [2, 4, 5, 4, 6]으로 이루어진 배열에서,

M이 8이고, K가 3일 때, 특정한 인덱스가 연속해서 세 번까지 더해질 수 있으므로,

6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46이 된다.

 

만약 [3, 4, 3, 4, 3]으로 이루어진 배열에서,

같은 수이지만 인덱스가 다르다면, 서로 다른 것으로 간주하기 때문에,

M이 7이고 K가 2라면,

4 + 4 + 4 + 4 + 4 + 4 + 4 = 28로,

두 번째 원소인 4와 네 번째 원소인 4를 번갈아 두 번씩 더하는 것이 가능하게 된다.

 

이 문제를 해결하려면, 우선 입력 값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다.

연속으로 더할 수 있는 횟수는 K번이므로, 가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다.

# N, M, K를 공백으로 받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int,input().split()))

data.sort() # 입력받은 수를 정렬하기
first = data[n-1] # 가장 큰 수, 배열의 마지막 인덱스
second = data[n-2] # 두번째로 큰 수, 배열의 마지막-1 인덱스

result = 0

while True :
	for i in range(k) : # 가장 큰 수를 K번 더하기
    	if m == 0 : #m이 0이라면 반복문 탈출
        	break
        result += first
        m -= 1 #더할 때 마다 1씩 빼기
    if m == 0 : #m이 0이라면 반복문 탈출
    	break
    result += second #두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 때 마다 m을 1씩 빼기
    
print(result) # 최종 답안 출력

 

4. 숫자 카드 게임

여러 개의 숫자 카드 중, 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임

1. 숫자가 쓰인 카드들이 N X M 형태로 놓여있다.

2. N은 행의 개수, M은 열의 개수를 의미한다.

3. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

4. 그 다음 선택된 행에 포함된 카드 중 가장 숫자가 낮은 카드를 뽑아야 한다.

 

즉, 이 문제는 각 행마다 가장 작은 수를 찾은 후, 그 수 중에서 가장 큰 수를 찾으면 된다.

 

이 문제는 리스트에서 가장 작은 원소를 찾아주는 min()함수를 이용할 수 있다.

# N, M을 공백으로 구분하여 입력받기

n, m = map(int, input().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) # 최종 답안 출력

이 문제는 이중 반복문을 사용해서도 해결할 수 있다.

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
	data = list(map(int, input().split())
    #현재 줄에서 가장 작은 수 찾기
    min_value = 10001
    for a in data:
    	min_value = min(min_value, a)
    # 가장 작은 수 들 중에서 가장 큰 수 찾기
    result = max(rsult, min_value)
    
print(result) # 최종 답안 확인

 

 

5. 1이 될 때 까지

어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택해서 수행한다.

2번째 과정은 N이 K로 나누어 질 때만 선택할 수 있다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

입력 조건

첫째 줄에 N과 K가 공백으로 구분되며 각각 자연수로 주어진다.

이 때, 입력으로 주어지는 N은 항상 K보다 크거나 같다.

 

출력 조건

N과 K가 주어질 때, 1번 혹은 2번을 수행하야 하는 총 최솟값, 횟수를 구하여라

 

이 문제는 최대한 많이 나누는 것이 중요하다.

n, k = map(int, input().split())
result = 0

# N이 K 이상이라면 K로 계속 나누기
while n >= k :
	# N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
    	n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1
    
#마지막에 남은 수에 대하여 1씩 빼기
while n > 1:
	n -= 1
    result += 1

print(result)