알고리즘 : 그리디 Greedy (탐욕법, 욕심쟁이 알고리즘)

본 글은 내가 '이것이 코딩테스트다 with 파이썬' 이라는 도서를 읽고 기록용으로 정리하는 것이다. 1회독을 할 때마다 글을 수정할 수도 있다.. (***내가 이해하기 쉽게 정리해놓은 글)

 

1회독

 

그리디 알고리즘이란?? 

그리디는 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 

여기서 탐욕적이라는 것은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

매 순간 가장 좋아 보이는 것을 선택하며 이 선택이 나중에 미칠 영향에 대해서는 생각하지 않는다.

 

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘으로 코딩테스트 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같이 알게 모르게 기준을 제시해준다. 대체로 이러한 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘은 정렬 알고리즘과 함께 출제된다.

 

---

 

예제) 거스름돈 문제 

  거스름돈으로 사용할 수 있는 돈 : 500원, 100원, 500원, 10원 짜리 동전 무한개 

  거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라 (단, N은 항상 10의 배수)

 

 

A. 가장 큰 화폐 단위부터 거슬러 준다.

 예를 들어, 500원 짜리를 거슬러 줄 수 있는 만큼 최대한 거슬러 주고, 그 다음 100원 그 다음 500원 .. 

 

  1) N이 1280원일 때 500원으로는 1000원을 만들 수 있다 ( 1280 / 500 의 몫 ) : 500원은 2개 

  2) 1번의 결과 나머지를 다시 100으로 나누어준다. ( 280 / 100 의 몫 ) : 100원 2개 

  3) 2번의 결과 나머지를 다시 50원으로 나누어준다. (  80 / 50 의 몫) : 50원 2개

  4) 3번의 결과 나머지를 다시 10원으로 나누어준다.  (30 / 10 의 몫) : 10원 3개

 

 

1~4번까지를 보면 반복적으로 몫은 동전의 개수가 되고 나머지는 다시 다음 단위로 나누게 된다.

이를 정리하면 몫은 동전의 개수 변수에 더해주면 되고 나머지는 다시 N에 저장하면 될 것처럼 생각이 든다. 

 

 

n = 1280
coin_sum = 0

coin_type = [500, 100, 50, 10]

for coin in coin_type:
	coin_sum += n / coin   # 몫은 그 cointype의 개수 -> coin_sum에 더해준다
    n %= coin # 나머지는 다음 계산을 위해 다시 n에 넣어준다


print(coin_sum)

 

 

실전1) 큰 수의 법칙

 

여기서 말하는 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 하지만 어떤 한 수를 연속적으로 더할 수 있는 횟수는 최대 K번이다. 

 

배열의 크기 - N

숫자를 더하는 횟수 - M

한 수를 연속적으로 더할 수 있는 최대 횟수 - K

일 때, N=5, M=8, K=3으로 주어지고 배열이 [ 2, 4, 5, 4, 6 ] 이라고 해보자.

 

그러면 가장 큰 수를 만들기 위해서는 배열에서 제일 큰 수를 더해야 한다고 생각이 들 것이다. 그렇다면 6을 선택해서 더하게 될텐데 6 + 6 + 6 을 하면 최대 횟수(3번)이 되었기 때문에 더이상 6을 더할 수 없다. 그렇다면 다음번으로 큰 수 5를 선택하여 더한다. (6 + 6 + 6 + 5)  6을 연속적으로 4번 더할 수 없는 것이고 5를 한번 더했기 때문에 다시 6을 더할 수 있다. 이러한 방식으로 8번을 더하면 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46, 답은 46이 된다.

 

이것을 그럼 코드로 작성해보자.

 

 

  * 단순 코드 * 

N=5,M=8, K=3

datalist = [2,4,5,4,6]

#제일 큰 수를 찾기 위해 sort
datalist.sort()

firstN = datalist[N-1] # 오름차순 정렬이기 때문에 가장 큰 수는 마지막 인덱스에 저장
secondN = datalist[N-2] # 그 다음 큰 수는 마지막인덱스-1 에 저장

sum = 0 // 합계 변수


while True : 
	for i in range(K): # K번만큼 가장 큰 수를 더해준다
    	if M == 0:
        	break; # M이 0이 되면 루프를 빠져나온다.
    	sum +=firstN
        M = M-1 #더하는 횟수를 한번 뺀다
    if M == 0:
    	break; # M이 0이 되면 루프를 빠져나온다.
    sum+=secondN  #두번째로 큰 수 더하기 
    M = M-1 #더하는 횟수를 한번 뺀다
       	

 

근데 이 방법은 M의 크기가 100억 이상으로 커지면 시간 초과 판정을 받게 된다. "반복되는 수열" 을 파악해서 코드를 작성할 수 있다.

 

 

 위에서 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46 으로 문제를 해결할 수 있다고 하였는데 자세히 보면 6+6+6+5가 두번 반복된 것이다. (가장 큰 수 K개 그 다음 큰 수 1개) 가 하나의 세트라고 볼 수 있다. 그러면 총 이 세트는 K+1개 인데 M을 K+1로 나누었을 때 몫이 이 세트가 반복되는 횟수이다. 그럼 가장 큰 수는 K * (M/K+1) 번 계산된다. 이것은 M이 K+1로 나누어떨어질 때이고, 나머지가 있는 경우도 고려해야한다. 나머지의 수만큼 가장 큰 수가 더 더해져야하기 때문에 총 firstN이 더해지는 횟수는  K*(M/ (K+1))+ M % (K+1) 이다. 그렇다면 그 다음 큰 수 secondN은  K*(M/ (K+1)) 만큼 더하면 된다. 

 

 

이것을 코드로 작성해보자

N=5,M=8, K=3

datalist = [2,4,5,4,6]

#제일 큰 수를 찾기 위해 sort
datalist.sort()

firstN = datalist[N-1] # 오름차순 정렬이기 때문에 가장 큰 수는 마지막 인덱스에 저장
secondN = datalist[N-2] # 그 다음 큰 수는 마지막인덱스-1 에 저장

sum = 0 # 합계 변수

# firstN가 더해지는 횟수

count = int(M/(K+1)) * K 
count += M % (K+1)  #나머지가 있을 때

#firstN을 count수 만큼 더하기

sum += count * firstN
sum += (M-count) * secondN # 나머지 횟수는 두번째로 큰 수를 더한다.