[Algorithm] Greedy Algorithm (그리디 알고리즘, 탐욕법)

@itsmo · January 08, 2023 · 7 min read

이 포스팅의 목표는 필자가 알고리즘을 공부하며 습득한 내용을 정리하는 데 있습니다. 따라서 틀린 내용이 있을 수 있습니다. 틀린 내용을 발견하신 경우 댓글로 지적해 주시면 감사하겠습니다.

Greedy Man
그리디 알고리즘은 현재 상황에서 가장 이득이 되는 방향으로 움직인다. 말 그대로 탐욕적으로.

1. 서론

그리디Greedy 알고리즘은 단순 무식하게, 현재 상황에서 최선의 선택만을 하는 알고리즘이다. 그리디 알고리즘은 매 순간 최선의 선택만을 하므로, 이후의 상황에 대해서는 전혀 고려하지 않는다.
그리디 알고리즘은 모든 상황을 고려하는 것이 아니기 때문에 시간을 크게 절약할 수 있다. 허나 그리디 알고리즘의 유형은 매우 다양하기 때문에, 특정 문제를 만났을 때 이 문제가 그리디 알고리즘으로 해결 가능한지를 파악할 수 있어야 한다.

2. 그리디 알고리즘의 조건

그리디 알고리즘을 사용하기 위해서는 크게 2가지 조건을 만족해야 한다.

  1. 탐욕스러운 선택 속성(Greedy Choice Property)

    현재의 선택이 이후의 선택에 영향을 주지 않아야 한다.

  2. 최적 부분 구조(Optimal Substructure)

    전체 문제의 최적 해결 방안이 부분 문제의 최적 해결 방안이어야 한다.

위 조건이 성립하지 않는다면, 그리디 알고리즘으로 해결할 수 없다.

3. 그리디 알고리즘의 정당성

그리디 알고리즘의 최선의 선택이라는 말이 어쩌면 말이 좋게 들릴 수 있겠지만, 현재 상황에서의 최선이기 때문에 오히려 함정에 빠질 수 있다. 예를 들어 보자.

3-1. 최소 경로 문제

그리디 알고리즘으로 풀 수 없는 문제
A에서 E로 가는 최소 경로를 그리디 알고리즘으로 구해 보자. 그리디로 푼 답과 실제 답이 일치할까?

위와 같은 그래프가 있다고 가정하자. 각 노드 사이의 간선은 다음 노드까지의 거리를 나타낸다. A에서 E로 가는 최소 거리는 얼마인가? 우리는 이미 머릿속에서 모든 경우의 수를 다 더해 보았기 때문에 A-D-E가 최소 경로임을 알지만, 이를 현재 상황만 고려하는 그리디 알고리즘으로 해결한다고 생각해 보고 문제를 들여다 보자.
A에서 B/C/D 각각의 노드로 이동하는 경로 중 최소 경로는 A-C이다. 그리디는 뒷일은 고려하지 않으므로 C로 가는 길을 택할 것이다.
문제는 다음 경로에 있다. C에서 도착지인 E까지 가는 경로는 거리 15짜리 길 단 하나다. 이렇게 되면 그리디 알고리즘은 3+15인 18이 최소 경로라고 답할 것이다.
당연하지만 이 문제는 그리디 알고리즘의 첫 번째 조건을 만족하지 못하기 때문에 그리디 알고리즘으로 풀 수 없다. 첫 번째 선택이 다음 경로 선택에 영향을 주기 때문이다.

3-2. 거스름돈 문제

가장 많이 나오는 그리디 알고리즘 문제의 예로는 거스름돈 문제가 있다. 일례로 N원을 500원, 100원, 50원, 10원 화폐 단위로 거슬러 줄 때, 이 거스름돈으로 N원을 만드는 데 필요한 화폐 개수의 최솟값을 출력하는 문제가 그것이다.
해당 문제는 큰 단위의 화폐부터 차례대로 거슬러 준다면 쉽게 해결이 가능하다. 그러나 이 문제는 거스름돈의 단위를 변경했을 때 그리디 알고리즘의 조건을 만족하지 않는 경우가 생긴다.
예를 들어 800원을 거슬러 줘야 하는데 화폐 단위가 500원, 400원, 100원인 경우를 생각해 보자. 그리디 알고리즘으로 풀이한다면 800원을 거슬러 주기 위해서는 500원 동전 한 개, 100원 동전 세 개로 총 네 개의 동전이 필요한 데 반해 실제 필요한 최소 동전의 개수는 400원 동전 두 개이다.
이 문제는 결국 큰 단위의 거스름돈이 작은 단위의 거스름돈의 배수가 되지 않기 때문에 그리디 알고리즘의 두 번째 조건을 만족하지 못한다. 따라서 이런 경우는 다이나믹 프로그래밍DP과 같은 다른 알고리즘으로 해결해야 한다.

4. 그리디 문제의 판별법

앞서 서술했듯 그리디 알고리즘의 유형이 매우 다양하기 때문에, 문제를 마주쳤을 때 뚜렷한 문제 유형이 파악되지 않으면 그리디 알고리즘으로 풀 수 있는지 의심해봐야 한다. 만약 그리디 알고리즘으로 해결할 수 없을 것 같다면, 이후에 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 풀이가 가능한 지 고민해보자.

5. 참고

  • 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020), p86-91.
@itsmo
배운 것을 잊지 않기 위해 틈틈히 기록합니다.