[Algorithm] 그리디(Greedy) 알고리즘

개요

최근 게임 회사 코딩테스트를 몇 번 경험해보니 그리디 알고리즘에 관한 문제가 적어도 1문제 이상 출시되었고, 많은 어려움이 있었기에 이번 포스팅에서는 그리디 알고리즘에 대해 자세히 정리해보도록 하겠습니다.

---

그리디 알고리즘

그리디 알고리즘(탐욕 알고리즘, Greedy Algorithm)은 매 순간 최선의 선택을 하여 문제를 해결하는 방법론입니다.

 

문제 해결 과정에서 한 번의 선택이 이후의 선택에 영향을 주기 때문에, 순간의 최적 선택이 결국 전체 문제의 최적 해답이 될 수 있다고 가정합니다.

 

즉, 각 단계에서 당장 최적인 해를 선택하고, 최종적으로 이러한 선택들이 모여 전체 문제의 최적 해답을 구성하는 방식입니다.

---

그리디 알고리즘 필요 조건

그리디 알고리즘을 사용하기 위해서는 다음의 두 가지 조건을 만족해야 합니다.

• 탐욕적 선택 : 각 단계의 선택이 이후 단계의 선택에 영향을 미치지않아야 합니다.
• 최적 부분 구조 : 문제의 최적 해가 부분 문제의 최적 해를 포함해야 합니다.

위의 조건을 만족하지 않는 문제인 경우 그리디 알고리즘이 최적의 해를 보장하지 못할 수 있으므로, DP 등 다른 방법을 고려해야 합니다. 저는 문제를 보면 무식하게 풀기(완탐) - DP - 그리디 순으로 생각합니다.

---

예시 문제

그리디 알고리즘의 대표적인 예시 문제는 "거스름돈"문제입니다.

 

문제 : 일정한 금액을 거슬러 주기 위해 최소한의 동전 개수를 사용하는 방법을 찾아보세요.

명제 : 가장 큰 가치의 동전부터 순서대로 선택하여 금액을 채우면 최소 동전 개수를 사용할 수 있습니다.

 

예를 들어 5300원이라는 돈을 거슬러줘야 한다고 생각해보도록 하겠습니다.

종류가 5000, 1000, 500, 100, 10원이 있다고 가정했을 때 최적의 해는 (5000 * 1) + (100 * 3) 입니다.

 

위 문제를 보고 단계별로 나눠보면 다음과 같습니다. (최적 부분 구조)

1. 가장 큰 화폐 단위부터 선택하여 부분 문제로 나누기
2. 선택된 화폐를 사용하고 남은 금액을 다음 단계의 문제로 넘기기
3. 1~2를 남은 금액이 0이 될 때까지 반복하며 전체 문제에 대한 최적 해를 찾기

위 문제를 풀기 위한 명제를 세우는 방법은 결국 경험에 의한 생각입니다. 즉, "가장 큰 가치의 동전부터 순서대로 선택하면 가장 적은 개수의 동전을 구할 수 있겠다." 라는 명제를 생각하고 실제로 값을 대입해보며 어느정도 맞는다고 생각이 되면 실제 문제 풀이를 진행하면 됩니다.

 

만약 답이 틀리다면 다시 처음 명제로 돌아와 명제를 수정해주는 방식으로 문제를 해결해 나가는 방식의 알고리즘이 그리디(탐욕) 알고리즘입니다.

---

결론

그리디 알고리즘은 문제를 푸는 데 있어 간단하고 빠르게 답을 구할 수 있는 방법입니다. 다만, 모든 경우에 최적의 해답을 보장하지 않으므로 문제의 조건을 잘 살피는 것이 중요합니다.