[Algorithm] Greedy 알고리즘 정복하기

kiteB·2021년 8월 26일

Algorithm-Python

목록 보기

1/7

[ 오늘의 주제는? ]

파이썬 정복하기🔥 두 번째 주제는 Greedy 알고리즘이다.

그리디 알고리즘은 사전에 외우지 않고 있어도 풀 수 있을 가능성이 높은 문제 유형이다.
그래프 탐색이나 정렬 같은 다른 알고리즘은 사용법을 알고 있어야 하지만,
그리디는 문제를 풀기 위한 아이디어만 잘 떠올려도 풀 수 있다!

그만큼 알고리즘 초보자가 풀기 좋은 문제이지만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓고, 아이디어를 떠올리는게 쉽지만은 않다.😢 그래서 많은 유형의 문제를 풀어보면서 연습해야 한다.

지금부터 그리디 알고리즘에 대해 자세히 알아보자!

[ Greedy 알고리즘이란? ]

Greedy 알고리즘은 일명 욕심쟁이 알고리즘이라고 불리며, 단순, 무식하게 지금 당장 좋은 것을 고르는 방법이다.

그리디 알고리즘을 사용하면 매 선택이 그 순간에서는 최적이지만 종합적으로 보았을 때 최적해임을 보장할 수는 없다. (물론 최적해일 경우도 있다.)

위의 설명들이 잘 와닿지 않을 수 있으니까, 예시와 함께 이해해보자!

그리디 알고리즘을 설명할 때 자주 등장하는 마시멜로 실험이다.

마시멜로 실험은 아이에게 마시멜로를 하나 주면서 "15분 뒤에 마시멜로가 그대로 있으면 하나 더 줄게."라고 하면서 아이의 행동을 관찰하는 실험이었다.

~~(물론 이 실험의 결론에 대해 여러 오류가 있다고 밝혀졌지만, 실험 자체만으로는 그리디 알고리즘을 설명하기 좋은 것 같다.)~~

시간과 관계없이 "마시멜로를 많이 먹기"를 목표로 그리디 알고리즘을 적용한다고 했을 때, 아이는 어떤 선택을 할까? 당연히 지금 당장 마시멜로를 먹을 것이다. 왜? 지금 할 수 있는 선택은 마시멜로 먹기 / 마시멜로 먹지 않기 밖에 없으니까!

그리디 알고리즘은 이 선택이 미칠 영향에 대해서는 관심없다.

지금 마시멜로를 먹지 않으면 15분 뒤에 하나를 더 줘서 총 2개를 먹는다는 사실을 전~혀~ 고려하지 않는다. 그냥 지금 이 순간에, 마시멜로를 먹는 것이 이득이라서 먹는 것이다.

결과적으로 보면, 2개 먹을 수 있는 마시멜로를 1개밖에 먹지 못했으니 최적해를 보장해주지 못한다.

[ Greedy 알고리즘을 사용하는 이유는? ]

그리디 알고리즘은 항상 최적해임을 보장할 수 없는데도 왜 사용하는 것일까?

모든 문제에서 최적해를 보장해주지 않지만, 특정 유형에서는 최적해를 보장해준다.
매우 빠르다.

그러므로 최적해를 구할 수 있는 문제에서는 그리디 알고리즘을 사용하면 빠르게 원하는 값을 얻을 수 있다.

[ Greedy 알고리즘의 정당성 ]

그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 없기 때문에, 그리디 알고리즘으로 문제를 해결했을 때의 답이 정당한지 검토해야 한다.

대표적인 예시인 거스름돈 문제를 통해 그리디 알고리즘을 사용할 수 있는지 알아보자.

📚 문제

당신이 편의점에서 일하는 점원이다. 카운터에는 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 하자. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하여라. 단, 거슬러 줘야 할 돈 N은 10의 배수이다.

이 문제의 key point는 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.

만약 N이 100이라면, 10원짜리로 10개나 50원짜리로 2개 거슬러주는 것보다 100원짜리 1개로 거슬러줄 때 최소 개수이기 떄문이다.

그러므로 N을 500원, 100원, 50원, 10원 순서대로 거슬러 줄 수 있을 만큼 거슬러준다.

(이처럼 그리디 알고리즘 문제는 가장 큰 순서대로, 가장 작은 순서대로 등의 기준을 알게 모르게 제시해주니까 잘 파악해보자😵)

📌 Code

이러한 아이디어를 이용하여 코드로 작성하면 다음과 같다.

n = 1260
cnt = 0

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

for coin in coins:
	cnt += n // coin   # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
	n %= coin          # 거슬러 준 만큼 n에서 빼주기

print(cnt)

이제 이러한 아이디어가 정당한지 한 번 생각해보자. 이 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 무엇일까?

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

예를 들어, 800원을 거슬러줘야 하는데 동전의 단위가 500원, 400원, 100원 이렇다면, 500원 * 1 + 100원 * 3의 조합으로 4개 거슬러주는 것보다 400원 * 2으로 2개 거슬러주는 것이 최소 개수일 것이다.

하지만 위의 예제(500, 100, 50, 10)의 경우, 큰 단위가 작은 단위의 배수 형태이므로 800(500, 400, 100)원의 경우와 같이 작은 단위의 동전일 때 최적의 값이 나오는 예외가 발생하지 않는 것이다!

이런 식으로 그리디 알고리즘으로 풀 수 있는지에 대한 판단을 잘 해야한다.

💡 Tip

어떤 알고리즘 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘 문제를 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자!
(앞의 선택이 이후의 선택에 영향을 주지 않고, 전체 문제를 부분적으로 해결할 수 있다면 그리디 의심!🤔)

만약 그리디로 해결할 수 없다면, 다이나믹 프로그래밍(DP), 그래프 알고리즘 등으로 문제를 해결해보자!