[파이썬] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

 

 

당장 좋은 것만 선택하는 알고리즘

 

"그리디(Greedy) 알고리즘은 단순하지만 강력한 알고리즘이다." - 이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

그리디(Greedy)란 단어를 번역하면 "탐욕스러운"이라는 뜻이다. 그리디 알고리즘을 말할 때 탐욕법이라고 불리는 이유이다. 여기서 '탐욕법'이라는 말의 뜻은 '현재 상황에서 가장 좋은 방법을 취하는 것'을 의미한다. 그리디 알고리즘을 이용하면 그 순간 '가장 좋은 것'만을 선택하여 적용하고, 그 이후의 상황은 고려하지 않는 것이다.

 

그리디 알고리즘과 다른 알고리즘을 비교했을 때 차이점은 다음과 같다. 다른 알고리즘을 사용하기 위해서는 사용법을 정확하게 알고 있어야 하지만, 그리디 알고리즘은 그렇지 않다는 것이다. 예를 들어 정렬에 관한 문제를 푼다고 할 때, 정렬에 관련된 라이브러리 사용법을 알고 있어야 하고, 최단 경로 문제를 풀 때는 다익스트라 알고리즘을 미리 알고 있어야 한다. 그러나 그리디 알고리즘은 문제의 폭이 넓어 암기를 통해 문제를 접근하는 데는 어려움이 있다.

 

그리디(Greedy) 알고리즘 문제를 풀기위해서는?

 

그리디 알고리즘은 문제 유형이 다양하기 때문에 암기를 통해 문제를 해결하기 어렵다(다른 알고리즘의 문제는 사용법, 적용 법을 알고 있다면 비슷하게 적용하여 해결할 수 있다). 사전 지식 없이 문제를 해결할 수 있지만, 그리디 알고리즘 유형의 문제를 풀기 위해서는 다양한 문제를 풀어보고 경험치를 쌓는 것이 좋다.

 

그리디 알고리즘 유형의 문제는 문제를 푸는 사람의 창의력을 요구한다. 해당 문제를 해결하기 위한 "최소한의 아이디어를 떠올릴 수 있는지?"를 물어보는 것과 같다. 앞서 언급한 것처럼 '가장 좋은 것'만을 선택하여 문제를 해결할 수 있는지 요구하는 것이다.

 

그리디 알고리즘은 가장 좋은 것을 선택하는 것이기 때문에 기준에 따라 가장 좋은 것을 파악해야 한다. 따라서 문제가 출제되면 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시하지 않고 문제가 출제되기도 한다. 난이도가 낮은 유형에서는 주어진 조건이 오름차순으로 정렬되어 주어지겠지만, 그렇지 않은 경우 주어진 조건을 오름차순으로 해결해야 하는지, 내림차순으로 해결해야 하는지, 다른 방법은 있는지 파악해야 한다.

 

그리디(Greedy) 알고리즘 예제

 

그리디 알고리즘의 대표적인 문제로 거스름돈 문제가 있다.

 

문제 설명

 

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

 

문제 풀이

 

GitHub - mieumje/Python_Coding_Test: Python Coding Test & Algorithm

 

n = int(input())
answer = 0

coins = [500, 100, 50, 10]

for coin in coins:
    answer += n // coin
    n = n % coin

print(answer)

 

가장 좋은 방법을 선택하는 아이디어를 우선 떠올려야 한다. 동전의 개수를 최소화해야 하기 때문에 가장 큰 단위의 동전을 많이 사용하고 가장 작은 단위의 동전은 적게 사용하는 것이 좋다. 가장 큰 동전부터 거슬러 주고 차례로 단위를 내려 적용하면 된다. 가능한 모든 500원을 거슬러 준 뒤 남은 금액에서 100원을, 다시 50원, 다시 10원 순으로 적용하면 된다.

 

이처럼 문제를 확인한 후 가장 좋은 방법이 무엇인지 파악하는 것이 중요하다.

 

시간 복잡도

 

거슬러 줄 수 있는 동전의 개수가 K일 때, '거스름돈' 문제의 시간 복잡도는 O(K)이다. 거슬러 주어야 할 돈 N은 시간 복잡도에 영향을 미치지 않는다.

 

그리디 알고리즘의 정당성

 

그리디 알고리즘을 통해 문제를 해결한 경우, 해당 방법이 정당한지 검토하는 과정을 거쳐야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있었던 이유는 갖고 있는 동전의 종류에서 가장 큰 금액의 동전이 항상 그 보다 적은 금액의 동전의 배수이기 때문에 가능하다.

 

예를 들어, '거스름돈' 문제에서 동전의 종류가 [500, 400, 100]이고 거슬러 주어야 할 돈이 800원인 경우 해는 4가 된다(500원 1개, 100원 3개). 그러나 최적의 해는 400원 2개를 거슬러 주는 2가 된다. 따라서 문제를 풀고 나서 정당성을 검토하는 과정은 반드시 필요하다.

 

---

 

문제를 해결할 때, 해당 문제의 유형이 정확하게 파악되지 않는 경우 우선 그리디 알고리즘을 떠올리고 접근해보는 것이 좋다. 그럼에도 문제를 해결하지 못했다면 DP나 그래프 알고리즘 등 다른 방법을 모색하여 문제를 해결한다.

 

 

---

그리디(Greedy) 유형 예제 

 

설탕 배달

 

2839번: 설탕 배달

 

GitHub - mieumje/Python_Coding_Test: Python Coding Test & Algorithm

 

N = int(input())
answer = 0

while N >= 0:
    if N % 5 == 0:
        answer += N // 5
        break
    N -= 3
    answer += 1

print(answer if N >= 0 else -1)

 

상근이는 5kg와 3kg의 봉지를 갖고 있다. 거스름돈 문제와 마찬가지로 5kg 봉지를 최대한 많이 사용하는 것이 가장 좋은 방법이다. 따라서 설탕의 무게를 5의 배수가 될 때까지 3씩 빼주며 정답에 1씩 더하고, 5의 배수가 되었을 때 정답에 5로 나눈 몫을 더해주면 된다. 

 

"만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다."라는 예외가 있기 때문에 마지막 정답을 출력할 때 조건을 걸어준다. 정확하게 N킬로그램을 만들 수 없다면 반복문을 마쳤을 때 N의 값은 음수가 되어있을 것이다. 따라서 음수가 아닐 때는 정답을 출력하고, 그렇지 않은 경우 -1을 출력한다.

 

---

 

ATM

 

11399번: ATM

 

GitHub - mieumje/Python_Coding_Test: Python Coding Test & Algorithm

 

def solution(N, P):
    answer = 0
    P.sort()
    tmp = 0
    for x in P:
        tmp += x
        answer += tmp
    return answer

N = int(input())
P = list(map(int, input().split()))

print(solution(N, P))

 

문제 설명 마지막 부분을 보면, "줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분 만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다."라고 적혀 있다.

 

가장 좋은 방법을 문제에서 설명해 주었기 때문에 그대로 구현만 해주면 된다. 주어진 입력값을 오름차순으로 정렬하고, 해당 리스트를 0번째(문제에선 1번째) 인덱스부터 순회하면서 값을 누적해 더해주기만 하면 된다.

 

 

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

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

이것이 취업을 위한 코딩 테스트다 with 파이썬 를 통해 공부한 내용을 정리한 것입니다.