[알고리즘] Greedy Algorithm(1)

저번학기 Data Algo & Analysis 수업에서 처음으로 Greedy 알고리즘에 대해 들어보았다. 가장 유명한 그리디 문제는 거스름돈 문제이다. Greedy라는 단어를 한국어로 직역하면 "탐욕적인" 이다. 그렇다면, 알고리즘에서 탐욕적이란것은 어떤것을 의미할까? 여기서 "탐욕적이다" 라는 말은, "현재 상황에서 최적의 해를 선택한다" 라는 말과 비슷하게 여겨진다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는(최적해)것을 선택하며, 현재의 선택이 나중에 영향을 미칠것은 생각하지 않는다.

 

 

그리디 알고리즘은 기준에 따라 좋은것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시 해 준다. 대체로 이 기준은 '정렬'을 이용했을때 손쉽게 풀리므로, 그리디 알고리즘은 자주 정렬 문제와 짝을 이룬다.

 

이제 위에서 언급한 "거스름돈" 문제를 통해 그리디 알고리즘이 뭔지 더 자세히 알아보자.

 

첫번째 문제 : 

출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬 by 나동빈

 

이 문제의 핵심 접근법은 "가장 큰 화폐 단위부터"돈을 거슬러 주는것이다. N원을 거슬러 줘야 할 때, 가장 큰 단위의 돈인 500원으로 거슬러 줄 수 있을만큼 거슬러 주는 것이다. 그 다음, 거슬러 줄 수 있는 범위 안에서 100원 - 50원 - 10원 순서대로 돈을 거슬러 주면 최소한의 동전으로 거스름돈을 줄 수 있다.

 

예를들어 , 우리가 거슬러 줘야 할 돈 N의 값이 1,260원 이라면, 최소한의 동전 갯수로 거슬러 줄 수 있는 경우는 다음과 같다.

 

(500 x 2) + (100 x 2) + (50 x 1) + (10 x 1)

 

위의 과정을 파이썬으로 구현한 코드는 다음과 같다.

 

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

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

 

대표적인 그리디 문제라 코드도 간결하고 간단하다. 그런데 사실 여기까지 풀고도 대략적인 감만 올 뿐, 문제가 좀 더 복잡하다면 훨씬 더 어려워 질 것 같은 느낌이다.

 

두번째 문제 : 

 

출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬 by 나동빈

 

아마 이 문제를 리트코드나 백준에서 봤다면 난 "그리디"를 떠올리진 못했을 것이다. 여기서 "그리디"를 떠올릴 수 있도록 문제를 해석 해 보자.

 

이 문제는 기본적으로 리스트가 인자로 주어지고, 추가적으로 변수 K, M이 주어진다. 이때, 이 리스트에서 M번의 횟수만큼 덧셈을 하여 최댓값을 구하여라. 단, 같은 인덱스에 있는 숫자는 K회 반복할 수 있다. 위의 문제를 예로 들어, 리스트가 [2,4,5,4,6], M = 8, K = 3과 같이 주어진다면, 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 가 이 문제에서 원하는 결과를 도출 할 수 있다.

 

- 문제가 원하는건 ? == 배열 안의 수를 M번 더했을때의 최댓값. 작은 값은 필요가 없다. 우리는 가장 큰 값과 두번째로 큰 값만 알고 있으면 된다. 그렇다면, 리스트를 정렬하면 맨 뒤의 숫자가 가장 큰 숫자일것이고, 이 숫자를 K번 까지만 연속으로 더할 수 있다. 그 다음은 맨 뒤 바로앞의 값을 1회만 더하고, 다시 가장 큰 값을 K번까지 반복하여 더해준다(M을 넘지 않는 선에서).  

 

아래는 위 문제의 파이썬 코드이다.

 

nums.sort()
firstMax = nums[-1]
secondMax = nums[-2]

result  = 0

for i in range(k):
	if m == 0:
    	break
    result += first
    m -= 1
if m == 0:
	break
result += second
m -= 1

return result

 

하지만 여기서 문제가 있다. 위의 예시에선 M이 10,000 이하이므로 이 방식으로 코드를 제출해도 통과를 하겠지만, M의 크기가 10,000 이상으로 커진다면 시간 초과 판정을 받을 것이다. 그렇다면, 더 효율적인 방법은 없을까?

 

아래는 간단한 수학적 아이디어를 포함한 설명이다.

 

- 위의 예시에서 가장 큰 수와 그 다음으로 큰 수는 6, 5 와 같다. 이 문제를 풀려면 먼저 "반복되는 수열"을 먼저 파악해야 한다. 가장 큰 수와 그 다음으로 큰 수가 더해질땐 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다. 위의 예시에서는 [5,5,5,6]이 된다( sum([5,5,5,6]) + sum([5,5,5,6]) == 46. 그렇다면 반복되는 수열의 길이는 어떻게 될까? 조금만 생각해보면  K + 1 이 된다는 것을 알 수 있다. 따라서 M을 수열의 길이 K + 1로 나눈것이 이 수열의 반복 횟수가 된다. 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다. 

 

- 이때 M이 K + 1로 나누어 떨어지지 않는 경우도 고려 해야한다. 그럴때는 M을 K + 1로 나눈 나머지 만큼 가장 큰 수가 추가로 더해지므로 이를 고려해야 한다. 즉, '가장 큰 숫자가 더해지는 횟수'는 다음과 같다.

 

int(M / (K + 1)) * K + M % (K + 1)

 

이를 토대로 작성한 파이썬 코드는 다음과 같다.

data.sort()  # 입력받은 수 정렬
first = data[n - 1]  # 가장 큰 수
second = data[n - 2]  # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += (count) * first  # 가장 큰 수 더하기
result += (m - count) * second  # 두 번째로 큰 수 더하기

print(result)  # 최종 답안 출력

 

세번째 문제 : 

 

이 문제는 결국 "각 행마다 가장 작은 수를 찾은 뒤, 그 수들 중 가장 큰 수를 찾아내기" 정도로 해석된다. 입력 조건에서 들어오는 모든 수는 10,000 이하이므로 단순히 배열에서 가장 작은 값을 찾는 기본 문법을 이용하여 각 행에서 가장 작은 수를 찾은 다음 그 수들중 가장 큰 수를 찾는 방식으로 문제를 해결 할 수 있다. 다음은 위 문제를 파이썬 코드로 구현한 것이다.

 

1. 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)  # 최종 답안 출력

 

2. 이중 반복문을 이용

# 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(result, min_value)

print(result)  # 최종 답안 출력

 

 

세번째 문제:

 

-내가 이 문제를 봤다면 Greedy를 생각 해내긴 어려웠을 것이다. 이 문제의 핵심 아이디어는 주어진 N에 대하여 '최대한 많이 나누기'를 수행하면 된다. 왜냐하면 어떠한 수가 있을때, '2 이상의 수로 나누는 것'이 '1을 빼는것' 보다 실행 횟수를 훨씬 많이 줄일 수 있기 때문(문제에서 요구하는 결과는 최소한의 실행횟수이므로)이다.(여기서 Greedy가 등장한다.) 문제에서는 K가 2 이상의 자연수 이므로, 가능하면 나누는 것이 1씩 빼는것 보다 훨씬 더 빠르게 계산 횟수를 줄일 수 있다.

 

예를들어, N이 9이고 K가 3이라면, 2번의 나눗셈으로 1을 만들 수 있다. 하지만, 여기서 나눗셈이 아니라 1씩 빼는 방법을 사용한다면, 8번의 계산을 해야 1이 된다. 4배나 많은 연산을 하는 셈이다.

 

다른 예를 들어보자. N이 25, K = 3일땐 다음과 같다.

 

1. N = 25(초기 상태)

2. N - 1 = 24

3. 24 // 3 = 8

4. 8 - 1 = 7

5. 7 - 1 = 6

6. 6 // 3 = 2

7. 2 - 1 = 1

 

6번의 과정으로 N = 1을 만들 수 있다. 그렇다면 위의 방법이 빠르게 동작하면서 그와 동시에 최적의 해를 보장한다는 것은 어떻게 알 수 있을까?

N = 27, K = 3일 때를 다시 생각해보자. 처음 3으로 나누었을 때는 27에서 18이 줄어들어 N = 9가 된다. 그다음에 3으로 나누었을 때는 9에서 6이 줄어들어 N = 3이 된다. 다시 말해 N이 클수록 K로 나누었을 때 줄어드는 양이 더 많다. N이 처음엔 큰 수라고 해도 나누기를 수행하면서 크기가 빠르게 줄어든다. 다시 말해 K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄일 수 있으며, N이 결국 1에 도달한다는 것을 알 수 있다. 그러므로 K로 최대한 많이 나눌 수 있도록 하는 것이 최적의 해를 보장하는 것이다.

파이썬을 이용해 작성한 답안 예시는 다음과 같다.

result = 0

while n >= k:
	while n % k != 0:
    	n -= 1
        result += 1  
    n //= k
    result += 1
    
while n > 1:
	n -= 1
    result += 1
    
return result