그리디 알고리즘

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.

그리디 알고리즘은 국내에서 그대로 번역하여, 탐욕법이라 부른다.
탐욕적이란, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

그리디 알고리즘을 이용하면 매 순간 가장 좋은 것을 선택하며,
현재의 선택이 나중에 미칠 영향은 고려하지 않는다.

코딩 테스트에서 그리디 알고리즘은 다른 알고리즘에 비해, 외우고 있지 않아도 풀 가능성이 높은 유형이다.
정렬, 최단 경로 등의 다른 알고리즘은 해당 알고리즘의 사용 방법을 정확히 알아야 해결 가능한 경우가 많다.

반대로 생각하면, 단순 암기를 통해 모든 문제를 대처하기 어렵다는 뜻이기도 하다.
많은 유형을 접해보고, 문제를 풀며 훈련을 해야한다.

예제) 거스름돈

카운터에는 거스름돈으로 사용할 동전 500원, 100원, 50원, 10원이 무한히 존재한다.
손님에게 거슬러 줘야 할 돈이 N원 일 때, 거슬러 줄 동전의 최소 개수를 구하라.

아이디어
가장 큰 화폐 단위부터 돈을 거슬러 준다.
큰 단위부터 거슬러 주며, 작은 단위로 차례대로 거슬러 줄 수 있는 만큼 주면,
최소 동전 개수로 거슬러 줄 수 있다.

코드

#python
def solution(n):
    count = 0
    coin_types = [500,100,50,10]
    
    for coin in coin_types:
        count += n // coin
        n %= coin
        
    return count

//js
function solution(n) {
    let count = 0;
    coinTypes = [500,100,50,10];
  
    for(let coin of coinTypes) {
    	count += Math.floor(n/coin);
      	n %= coin
    }
  
    return count; 
}

그리디 알고리즘의 정당성

모든 문제에 그리디 알고리즘을 적용할 수 있는 것은 아니다.
대부분의 문제에서 그리디 알고리즘을 이용하면, 최적의 해를 찾을 수 없을 가능성이 높다.

그리디 알고리즘으로 해법을 찾았을 때는, 정당한지 검토해야 한다.

이 문제에서 그리디 알고리즘으로 해결할 수 있었던 이유는,
작은 단위를 조합해 다른 해가 나올 수 없기 때문이다.

n이 800인데 화폐 단위가 '500원 400원 100원' 이라면,
그리디는 500+100+100+100 4개지만, 최적의 해는 400+400 2개이다.

이처럼, 대부분의 그리디 알고리즘 문제는 풀이를 위한 아이디어를 떠올리고, 정당한지 검토할 수 있어야 한다.

문제의 유형이 파악하기 어렵다면, 그리디 알고리즘을 의심하고, 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자.

연습문제

큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때, 주어진 수를 m번 더해 가장 큰 수를 만든다.
단, 특정 인덱스에 해당하는 수가 k번을 초과하여 더해질 수 없다.
가장 큰 수를 구하라.

아이디어
k번 만큼 가장 큰수를 더하고, 1번 그 다음 큰 수를 더한다.

def solution(arr, m, k):
    arr.sort(reverse = True)
    first = arr[0]
    second = arr[1]
    
    result = 0
    while True:
       for i in range(r):
           if m == 0: break
           result += first
           m -= 1
           
        if m==0: break
       	result += second
        m -= 1

추가로, 더해지는 값이, 일정 수열의 반복이라는 것을 알 수 있다.

수열이 반복되는 횟수는 int(m/(k+1)), 가장 큰 수가 더해지는 횟수는 int(m/(k+1)) *k
나누어 떨어지지 않을 때는, 나머지만큼 가장 큰 수가 더해진다.

두 번째 큰 수가 더해지는 횟수는, 가장 큰 수가 더해지는 횟수로 구할 수 있다.

#python
def solution(arr, m, k):
    arr.sort(reverse = True)
    first = arr[0]
    second = arr[1]
    
    count = m//(k+1) *k
    count += m%(k+1)
    
    result = 0
    result += first * count
    result += second * (m-count)
    
    return result

//javscript
function solution(arr, m, k) {
    arr = arr.sort((a,b) => b-a)
    const first = arr[0]
    const second = arr[1]
    
    let count = Math.floor(m./(k+1)) *k
    count += m%(k+1)
  	
    let result = 0
    result += first * count;
    result += second * (m-count);
    
    return result
    
}