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

그리디 알고리즘이란?

그리디 알고리즘은 여러 경우 중 가장 최적이라고 생각되는 것을 선택하여 진행하는 알고리즘이다.

그리디 알고리즘을 적용하기 위해선 2가지 조건을 성립해야 한다.
1. 탐욕적 선택 조건(greedy choice property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조 조건(optimal substructure): 문제에 대한 최적해가 부분 문제에 대해서도 최적해이다.

위의 두 조건을 성립하지 못한다면 대부분 최적의 해를 구할 수 없다.

그렇기에 그리디 알고리즘은 항상 최적의 해를 도출하는 것은 아니지만 최적에 근사한 값을 빠르게 도출 할 수 있다는 장점이 있다.

그리디 알고리즘 풀이 과정

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

그리디 알고리즘 예시

거스름돈 동전의 최소 개수

4780원의 상품을 구입하는데 5000원 지폐를 건냈다고 가정한다.
이 때 받을 수 있는 동전의 최소 개수를 구하라.

1. 선택 절차
   가장 가치가 높은 동전을 우선 선택한다. ex) 500원

2. 적절성 검사
   1번 과정에서 나온 동전이 거슬러 줄 금액을 초과하는지 검사한다.
   초과 한다면 다시 1번으로 돌아가 더 작은 동전을 선택한다.

3. 해답 검사
   선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
   부족하다면 다시 1번으로 돌아간다.

위 과정에서 1번의 동전의 선택 과정을 보면 다음과 같다.

500 -> 100 -> 500 -> 100 -> 500 -> 100 -> 10 -> 500 -> 100 -> 10

1번에서 동전을 선택할 때 전의 부분 해답이었던 동전보다 큰 값은 절대 나오지 않으므로 선택하는 절차에 적용한다면 다음과 같이 줄일 수 있다.

500 -> 100 -> 100 -> 100 -> 10 -> 10

무게가 제한된 가방에 가치가 높은 물건 담기

20kg까지 담을 수 있는 가방에 각 무게와 가치가 있는 물건을 담되 담긴 물건의 총 가치가 가장 높은 경우를 구해라

1) 20kg 200$ 그림
2) 1kg 20$ 반지

1. 선택 절차
   가장 가치가 높은 그림은 선택한다.

2. 적절성 검사
   1번 과정에서 나온 물건이 가방 무게를 초과하는지 검사한다.

3. 해답 검사
   가방을 더 채울 수 있다면 1로 돌아간다.

1번에서 가치가 가장 높은 그림을 선택한다면 가방을 더욱 채울 수 없으므로 종료한다.

하지만 그림 하나보다 반지 20개를 채우는 것이 가치가 더 높다.

즉 그리디 알고리즘으로 최적 해를 구할 수 없다.

이와 같이 그리디 알고리즘이 항상 최적의 결과를 보장하지 못한다.
탐욕적 선택 조건과 최적 부분 구조 조건이 성립해야 그리디 알고리즘을 통해 최적의 해를 구할 수 있다.