[이코테] 그리디 알고리즘

그리디 알고리즘 (탐욕법)

• 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시함

 

 

[ 예제 3-1 ] 거스름돈

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

문제 접근

1. '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이 아이디어의 핵심
2. 예를 들어 N원을 거슬러 준다고 할 때, 500원으로 거슬러 줄 수 있을 만큼으로 거슬러 준 후 그 다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 준다면 최소 동전의 개수만 사용 가능
3. 큰 화폐단위가 항상 작은 화페단위의 배수 형태인 경우라면 최적의 해를 보장할 수 있음

#예제 3-1 거스름돈 파이썬 풀이법
n = 1260
count = 0

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

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

 

시간복잡도

: 화폐의 종류만큼 반복 수행 해야하기 때문에 화폐의 종류가 K개라고 할 때 소스 코드의 시간 복잡도는 O(K)

: 즉 동전의 총 종류에만 영항을 받고, 거슬러 줘야하는 금액의 크기와는 무관함

 

 

그리디 알고리즘의 정당성

• 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 함
• 거스름돈 문제가 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
• 800원을 거슬러 줘야 할 때  화폐 단위가 500원, 400원, 100원인 경우를 생각하면 그리디 알고리즘으로 4개의 동전(500원 + 100원 + 100원 + 100원)을 거슬러 줘야 한다고 나오는데 최적의 해는 2개의 동전 (400원 + 400원)을 거슬러 주는 것임
• 큰 단위가 작은 단위의 배수 형태이므로, '가장 큰 단위의 화폐부터 가장 작은 단우의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다'는 아이디어는 정당함
• 대부분의 그리디 알고리즘문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검출할 수 있어야 답을 도출할 수 있음
• 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는 지 고민해보자. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면 그 때는 다른 알고리즘으로 문제를 해결할 수 있는지 재차 고민해보는 것도 한 방법임

 

[ 예제 3-2 ] 큰 수의 법칙

입력 조건

• 첫째 줄에 N(2 <= N <= 1000), M(1 <= M <= 10000), K(1<= K <= 10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단 각각의 자연수는 1이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

입력 예시 5 8 3 2 4 5 4 6

출력 예시 46

 

 

문제 접근 1 ( 단순하게 풀기)

: 이 문제를 해결하기 위해서 일단 입력 값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다 연속으로 더할 수 있는 횟수는 최대 K번 이므로 '가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산'을 반복하면 됨

 

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

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

result = 0

while True:
	for i in range(k):	# 가장 큰 수 K번 먼저 더하기
    	if m == 0:
        	break
        result += first
        m -= 1	# 더할 때마다 1씩 빼기
    if m == 0:
    	break
    result += second
    m -= 1	# 더할 때마다 1씩 빼기


print(result)

: 이 문제는 M이 10,000 이하이므로 이 방식으로 문제 해결 가능하지만, M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 수 있음 따라서 간단한 수학적 아이디어를 활용한다면 더 효율적으로 문제 해결이 가능함

 

 

 

문제 접근 2 ( 더 효율적인 방법)

2

4

5

4

6

이 때 가장 큰 수는 6이고 두 번째로 큰 수는 5이다.

6

6

6

5

예를 들어,N = 5, M = 8 이고 K =3일 때 합을 구성할 수 있는 수가 2, 3, 5, 4, 6이라면 위와 같이 더했을 때가 합을 최대로 할 수 있다.

즉, ( 6 + 6 + 6 + 5 )가 2번 반복해서 정답이 46이 된다. 

 

 

• 이 문제의 처음 접근 방식은 반복되는 수열에 대해서 파악해야함
• 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있음
• 반복되는 수열의 길이는 ( K + 1 )
• 수열이 반복되는 횟수는 M / ( K + 1 ) 이며, 여기에 K를 곱하면 가장 큰 수가 등장하는 횟수
• M이 ( K + 1 ) 로 나누어 떨어지지 않는 경우도 고려할 때 M을 ( K + 1 ) 로 나눈 나머지만큼 가장 큰 수가 추가로 더해짐
• 즉 '가장 큰 수가 더해지는 횟수'는 int( M / ( K + 1 ) ) * K + M % ( 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
count += m % (k+1)

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

print(result)

 

 

 

 

Ellen's thinking

이 책의 저자가 소개하듯이, 알고리즘 문제를 처음 마주할 때 그리디 알고리즘인지 의심하고 고민해야겠다. 그러나 시간이 오래 지날 수록 해결법이 떠오르지 않는다면 다이나믹 프로그래밍이나 그래프 알고리즘을 떠올려서 문제를 풀어야한다. 또한 그리디 알고리즘으로 풀 때 단순히 해결법만 생각해서 소스코드로 구현한다면 그 방식이 틀릴 수 있다. 따라서 자신이 생각한 해결법이 최적의 해를 보장하는지 근거까지 도출할 수 있어야한다. 그리디 알고리즘은 여러 문제를 풀어보며 익혀야 할 것 같다.