그리디(Greedy) 알고리즘

 

1.  그리디(Greedy) 알고리즘 이란?

그리디 알고리즘이란 문제를 해결하는 과정에서 매 순간 가장 최선인 선택을 하는 알고리즘이다.

그리디는 우리말로 탐욕이라는 뜻으로 국내에서는 "탐욕 알고리즘"이라고 칭하기도 한다.

그리디 유형의 문제는 타 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀 수 있는 가능성이 가장 높은 유형이라는 특징이 있다.

 

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

그렇기 때문에 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 한다.

 

---

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

그리디 알고리즘은 두 가지 조건이 성립해야 적용할 수 있다.

 

1) 탐욕 선택 속성

매 단계에서 가장 최적의 선택을 함으로써 전체 문제의 최적해를 구할 수 있다는 성질이다.

즉, 매번 가장 좋은 선택을 하면, 그 선택이 결국 전체 문제의 최적해로 이어진다고 보장하는 것이다.

 

2) 최적 부분 구조

문제의 최적해가 부분 문제의 최적해로부터 구성될 수 있다는 성질이다.

즉, 주어진 문제를 해결하기 위해서 그 문제를 더 작은 부분 문제로 나누고, 그 부분 문제들을 해결한 후 전체 문제를 해결하는 방식이다.

 

---

3. 그리디 알고리즘 문제를 해결하는 방법

1) 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.

 

2) 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.

 

3) 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

---

4. 예시 문제

 

'거스름돈' 문제는 그리디 알고리즘을 대표하는 문제이다.

 

- 문제 

당신은 계산을 도와주는 카운터 점원이다.

주어진 금액을 거슬러줄 때, 가능한 가장 적은 동전 개수를 사용하여 거슬러주기 위한 방법을 구하는 문제이다.

예를 들어, 동전의 종류가 500원, 100원, 50원, 10원이고, 목표 금액이 760원이라면,

그리디 알고리즘을 사용하여 가장 적은 동전 개수를 구할 수 있다.

 

- 접근 방법

가장 큰 동전부터 차례로 사용하면 된다. (탐욕적)

거슬러줄 금액에서 가장 큰 동전으로 최대한 거슬러주고, 그 후 남은 금액을 처리하는 방식으로 처리한다.

 

- 풀이

1) 500원을 최대한 사용: 760 // 500 = 1번 (500원 1개 사용, 남은 금액 260원)

2) 100원을 최대한 사용: 260 // 100 = 2번 (100원 2개 사용, 남은 금액 60원)

3) 50원을 최대한 사용: 60 // 50 = 1번 (50원 1개 사용, 남은 금액 10원)

4) 10원을 사용: 10 // 10 = 1번 (10원 1개 사용, 남은 금액 0원)

 

따라서, 최소 동전 개수는 1 (500원) + 2 (100원) + 1 (50원) + 1 (10원) = 5개이다.