[Algorithm] Greedy

[jane1choi]

Greedy 알고리즘이란?

greedy는 '탐욕스러운, 욕심 많은' 이라는 사전적 의미를 갖고 있습니다.
greedy 알고리즘은 탐욕 알고리즘으로도 불리는데, 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다. 즉, 현재 선택에서 최적인 것들을 마지막 선택까지 해나가서 답을 구하는 알고리즘입니다.

하지만 이 방법으로 문제를 해결할 경우, 해당 순간의 선택은 그 당시 최적(local optimal)일 수 있으나, 최종적으로 최적(globally optimal) 이라는 보장은 없기 때문에 local optimal이 global optimal을 보장하는지 확인하는 과정을 거쳐야 합니다.

Greedy 알고리즘 조건

greedy 알고리즘은 다른 방법들 보다 빠른 속도때문에 적용할 수 있다면 가장 빠르게 결과를 얻을 수 있습니다.
그렇다면 빠르게 탐욕 알고리즘이 적용 가능한지 파악하는 것이 중요한데, 어떤 문제들에 greedy 알고리즘을 적용할 수 있을까요??
greedy 알고리즘을 적용하기 위해 필요한 조건은 2가지가 있습니다.

1. 탐욕스러운 선택 조건 (Greedy Choice property)

탐욕적인 선택 조건이란 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것입니다.

탐욕 알고리즘의 대표적인 문제인 거스름돈 문제를 통해 살펴보겠습니다!

만약 손님이 10,000원을 가지고 있다고 가정할 때,
나는 가게의 점원으로 계산할때 잔돈은 항상 적은 개수의 동전을 주어야 한다.
동전은 10원, 50원, 100원, 500원이 있을때,
물건 값이 입력 될때 잔돈의 최소 동전 개수를 구하라.
(동전의 개수는 충분한 상황)

위의 문제에서 손님이 5250원짜리 물건을 구매했다고 하면, 잔돈은 4750원이 됩니다.
1000원 단위는 제외하고 750원을 동전으로 주어야 하는 상황에서 아래와 같은 과정으로 동전의 개수를 구할 수 있습니다.

• 750원
  • 최적의 선택 500원 차감 동전 개수 : 1
• 250원
  • 최적의 선택 100원 * 2개 차감 동전 개수 : 2
• 50원
  • 최적의 선택 50원 차감 동전 개수 : 1

-> 최소 동전은 4개

이 과정에서 동전을 고르는 행위는 현재의 남은 금액에 따라 선택을 하기 때문에 내가 500원을 선택 한 앞의 행위는 다음 선택에서 100원을 선택하는 것에 영향을 주지 않습니다.

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

작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다.
이 말은 전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 하나 하나의 단계에 대해 최적해를 도출해서 전체 문제의 해를 도출해야 된다는 것입니다.

위의 문제를 다시 가져와보겠습니다!

• 750원
  • 최적의 선택 500원 차감 동전 개수 : 1
• 250원
  • 최적의 선택 100원 * 2개 차감 동전 개수 : 2
• 50원
  • 최적의 선택 50원 차감 동전 개수 : 1

-> 최소 동전은 4개

최종적으로 750원에서 최소한의 동전 개수를 구하는 문제(전체 문제)는 현재 남은 금액(750원, 250원, 50원)보다 작으면서 가장 단위가 큰 동전의 최대 개수 구하기 문제(부분 단계)의 개수 합으로 구할 수 있으므로 최적 부분 구조를 만족합니다.

최소 동전의 개수를 구하는 문제는 사실상 거스름돈 금액에서 조합 가능한 가장 큰 금액의 동전의 조합을 찾아서 그 개수를 구하는 문제입니다.
이를 부분 문제로 쪼개면 현재 금액보다 작으면서 가장 큰 금액의 동전을 찾고 이를 현재 금액에서 빼주고 개수를 세주면 됩니다.
이 단계를 합쳐서 최종 해까지 도출 할 수 있기 때문에 최적 부분 구조 조건을 만족하는 것입니다.

Greedy 알고리즘 문제를 해결하는 방법

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

참고 자료: https://velog.io/@gillog/탐욕-알고리즘Greedy-Algorithm, https://velog.io/@contea95/탐욕법그리디-알고리즘