[Algorithm 완전 정복] 지금 당장 좋은 것만 고르는 그리디 greedy

이 글은 <이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈, 한빛미디어)>를 읽고 이해한 바를 바탕으로 작성되었습니다.

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

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

📌그리디 알고리즘

그리디greedy 알고리즘은 '지금 당장 좋은 것만을 고르는 방법'이다.

문제에서 '가장 큰 순서대로, 가장 작은 순서대로'같은 기준을 은연중에 제시해준다. (이 조건들이 정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많다!)

 

그리디 알고리즘은 '정당성' 분석이 중요하다.

단순히, 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토해야한다.

 

 

✅예제) 거스름돈

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

이 문제가 그리디 알고리즘 유형의 대표적인 문제가 될 수 있는 이유는 '가장 큰 화폐 단위부터' 돈을 거슬러 주어야 하기 때문이다. (가장 좋은 것부터! 가장 큰 것부터!) 그래야지 최소의 동전을 사용하여 거슬러 줄 수 있을테니까!

n = int(input())
count = 0

list = [500, 100, 50, 10] #큰 단위의 화폐부터 확인

for coin in list:
	count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전 개수 (몫)
	n % = coin #큰 동전으로 바꾸고 난 나머지

print(count)

• list의 큰 단위의 동전부터 차례대로 확인한다.
• n을 동전 단위로 나눈 몫을 count에 더하고, 
• 나머지를 남은 금액(n)으로 할당한다.
• 시간복잡도: O(k) ((화폐종류 k개))
  ↳ 시간복잡도가 거슬러 주어야 할 금액 N과는 무관하게 화폐 단위의 종류의 개수(k)에만 영향을 받는다.

 

✅BOJ #5585

백준에도 비슷한 문제가 있길래,,!

5585번: 거스름돈

pay = int(input())
change = 1000 - pay
coins = [500, 100, 50, 10, 5, 1]
cnt = 0

for coin in coins:
    cnt += change // coin
    change %= coin
    
print(cnt)

((거의 똑같,,))

 

 

📌그리디 알고리즘의 정당성

탐욕적으로 문제에 접근했을 때, 정확한 답을 찾을 수 있다는 보장이 있을 때 매우 강력한 풀이 방법이다.

따라서 정당성 분석이 중요하다.

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

동전 단위가 배수 형태가 아니라면, 그리디 알고리즘으로 풀 수 없다!

그 예시로 백준의 #14916 문제가 있다.

14916번: 거스름돈

이 문제는 거스름돈의 단위가 2원과 5원으로 배수 형태가 아니다. 따라서 이 문제는 그리디 알고리즘으로 해결할 수 없다. (풀이는 곧,,..!(*/ω＼*))

 

✅문제) 큰 수의 법칙

다양한 수로 이루어진 크기가 N X N인 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없음
ex) 5 8 3 (N, M, K가 주어짐)
     2 4 5 4 6
     → 정답) 6+6+6+5+6+6+6+5=46

이 문제의 접근 방법은 배열에서 가장 큰 수를 K번 더하고, 두번째로 큰 수를 한번 더해주고 또 가장 큰 수를 K번 더해주고,.. 이 과정을 계속 반복한다.

언제까지? → 숫자가 총 M번 더해질 때까지!

 

#풀이1

n, m, k = map(int, input().split())

data = list(map(int, input().split()))
data.sort()
answer = 0

first = data[n-1]
second = data[n-2]
#sorting해서 제일 큰 수와 두번째로 큰 수 확인하기

while True:

#-----------------
    for i in range(k):
        if m == 0:
            break #아직 K번 다 안돌렸는데도 M번이 다 더해졌음 -> 종료
        answer += first #가장 큰 수를 K번 더하기
        m -= 1 #더할 때마다 총 숫자를 더해야 하는 횟수 M에서 1씩 빼기
#-----------------K번 돌리는 과정
    
    if m == 0:
        break #K번 다 더해지고 M번 다 더해졌음 -> 종료
#----------------K번 후 M도 같이 끝남
    
    answer += second #K안에서 M이 다 해결이 안될 때, 두번째로 큰 수를 한번 더해주고 다시 반복
    m -= 1 #두 번째 수도 더할 때 M-1
#----------------K번 후 M이 남음

print(answer)

 

#풀이2

조금 더 생각해보면 파악할 수 있겠지만, 더해지는 과정은 항상 K번의 첫번째로 큰 수와 1번의 두번째로 큰 수가 반복되는 수열의 형태를 가진다.

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[n-1]
second = data[n-2]

count = int(m/(k+1))*k #수열 안에서 first가 더해져야 하는 횟수 (수열이 반복되는 횟수 * 수열 안에서 반복되는 횟수)
count += m%(k+1) #수열 밖에서 first가 더해져야 하는 횟수

result = 0
result += (count) * first
result += (m-count) * second

#(한줄에 한번에 쓰기도 가능!)
#result = ( (m // (k+1)) * k + (m % (k+1)) ) * first + ( m // (k+1) ) * second

print(result)

• 반복되는 수열 → K번의 first와 1번의 second
  : { first, first, ..., first, second } 
• 수열이 반복되는 횟수 → 총 숫자가 M번 더해져야하고, 수열 안이 숫자의 개수는 K+1이기 때문에
  : M // ( K + 1 )
• 나머지 숫자들 → second까지 못가서 완엇된 전체 수열이 들어가지 못했다는 얘기니까 나머지 더해져야 하는 횟수만큼 first 더해주기
  : first * ( M % ( K+1 ) )

 

✅문제) 숫자 카드 게임

숫자 카드 중 가장 큰 숫자 카드 뽑기 게임
숫자 카드 N X M 형태
뽑고자 하는 카드가 포함된 행을 선택 후, 선택된 행에 포함된 카드들 중 가장 작은 카드를 뽑아야 하는 것이 게임의 규칙

→ 즉, 게임에서 이기려면 각 행에서 가장 작은 수들 중에서 가장 큰 수를 찾아야 게임에서 이길 수 있다.

 

#풀이1) min() 함수를 이용한 답안 예시

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

for i in range(n): #한 행씩 확인
    data = list(map(int, input().aplit()))
    min_value = min(data) #현재 줄에서 '가장 작은 수 찾기'
    result = max(result, min_value) #'가장 작은 수'들 중에서 가장 큰 수 찾기
    
print(result)

 

#풀이2) 2중반복문 구조를 이용한 답안 예시

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

for i in range(n): #한 행씩 확인
    data = list(map(int, input().split()))
    min_value = 10001 #(모든 숫자는 10000이하인 것이 조건)
    for a in data:
        min_value = min(min_value, a) #한 행에서 가장 큰 수 찾기
    reuslt = max(result, min_value) #가장 작은 수들 중에서 가장 큰 수 찾기

풀이1이 풀이2보다 훨씬 쉽고 직관적이라고 생각한다. 굳이 왜 풀이2를 써야하지..? 이런 생각...

 

✅문제) 1이 될 때까지

어떤 수 N이 1이 될 때까지 두 과정 중 하나를 반복 수행
1. N에서 1을 뺀다.
2. N을 K로 나눈다. (N이 K로 나누어 떨어질 때만 선택 가능)

N이 1이 될 때까지 1번 또는 2번의 과정을 수행해야하는 최소 횟수는?

→ K가 2이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄일 수 있다. 따라서 K로 최대한 많이 나눌 수 있도록 하는 것이 최소 수행 횟수를 보장한다.

 

#풀이1

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

while n >= k: #N이 K이상이라면 K로 나누는 옵션이 항상 존재
    while n % k != 0: #N이 K로 나누어 떨어지지 않는다면 n에서 1씩 빼기
        n -= 1
        result += 1
    n //= k
    result += 1
    
while n > 1: #N이 K보다 작은데 1 이상이라면
    n -= 1 #1이 될 때까지 계속 1을 빼기
    result += 1
    
print(reuslt)

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

while True: #N이 K로 나누어 떨어지느 수가 될 때까지 1을 빼기
    target = (n // k) * k #K로 나누어 떨어지는 값
    result += (n - target) #target이 될 때까지 뺀 값을 result에 더해주기 (1을 빼주는 수행 횟수를 한번에 계산)
    n = target
    if n < k: #N이 K보다 작아서 더이상 나눌 수 없으면 반복문 탈출
        break
    result += 1 #N을 K로 나눈 수행 횟수 더하기
    n //= k #N을 K로 나누기
    
result += (n-1) #while문 탈출 후, N이 1이 될 때까지 1씩 빼주는 수행을 한번에
print(result)