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

그리디 알고리즘 

그리디 알고리즘은 Greedy(탐욕, 욕심쟁이)라는 이름처럼 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다.

그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 가장 최선의 선택을 하는 기법이기 때문에 종합적인 결과에 대해서는 최적의 해를 보장할 수 없다. (지역적(local)으로는 최적의 선택이지만 이를 반복하더라도 전체적(global)으로는 최적의 해가 아닐 수 있음)

---

그리디 알고리즘의 장점

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.

 

탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다. 그래서 실용적으로 사용할 수 있다.

---

그리디 알고리즘의 문제 풀이법

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

 

 

👉탐욕 알고리즘을 적용하기 위한 2가지 조건

그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 다음 두 조건을 만족한다.

1. 탐욕적 선택 속성(greedy choice property): 현재 선택이 이 후의 선택에 영향을 주지 않음

2. 최적 부분 구조(optimal substructure): 매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 함

 

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못함..

 

 

 

---

❗️탐욕 알고리즘을 일상 예시 1 – 매트로이드

하나몬은 오늘도 편의점에서 열심히 아르바이트하고 있다.
손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔다.
박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였다.

👉 이때 하나몬은 어떻게 거슬러 주어야 할까?

• 탐욕 알고리즘으로 동전의 개수를 헤아리는 일은 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일하다.
• 거스름돈 960원을 채우기 위해서 먼저 500원짜리 동전을 한 개를 선택한다.
• 그다음은 100원짜리 동전을 네 개 선택하고, 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택할 것이다.

👉 탐욕 알고리즘의 문제 해결 과정을 적용

1. 선택 절차
   • 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 적절성 검사
   • 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다.
   • 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
3. 해답 검사
   • 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
   • 액수가 부족하면 1번 과정부터 다시 반복한다.

👉 이 과정을 통해 얻은 문제에 대한 해답

• 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 준다.

이 문제 구조는 매트로이드이다. 탐욕 알고리즘을 사용해도 언제나 최적해를 찾아 낼 수 있다.