[Algorithm] 그리디 탐욕 (Greedy)

그리디 알고리즘(Greedy), 탐욕법이란?

선택의 순간마다 당장 눈앞에 보이는 최적의 답을 골라 최종 해답에 도달하는 방법론

아래의 사진에서 가장 큰 값을 구해야 한다면?

• 그리디는 현재 상황에서 최적의 답을 구할 뿐, 최종 해답에 도달한 답이 가장 좋은 답임을 보장하지는 않음

그렇다면 그리디 알고리즘을 어떻게 믿고 쓸 수 있지?

• 이를 위해서 문제가 아래 활용 조건 2개를 만족하는지를 따져보고, 적용 가능한 문제에서만 활용
• 아래의 조건 2개가 만족된 구조를 매트로이드라고 함.
• 어떤 문제가 매트로이드 구조라는 것은 최종 해답에 도달한 답이 가장 좋은 답임을 보장함
• 따라서 그리디를 적용할 수 있는 문제는 항상 최적해를 구하는 문제가 됨

---

등장 배경 : 동적 계획법

• 간단한 문제의 경우, 동적 계획법은 지나치게 많은 일을 수행하는 문제 발생

---

[활용 조건]

어떤 경우에서 활용할 수 있을까?

 

DP를 사용하기 위해서는 아래 두 가지의 조건이 만족되어야 함

 

1. 탐욕적 선택 속성

• 앞의 선택이 후의 선택에 영향을 주지 않음, 모든 선택은 독립적임

 

2. 최적 부분 구조 (Optical Substructure)

• 최종 문제 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됨
• 즉, 부분의 최적해 집합이 전체 문제의 최적해여야 함

---

[해결 절차]

1. 선택 절차(Selection Procedure)

• 현재 상태에서 최적의 해답 선택

 

2. 적절성 검사(Feasibility Check)

• 선택된 해가 문제의 조건을 만족하는지 검사

 

3. 해답 검사(Solution Check)

• 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택 절차로 돌아가 위의 과정 반복

---

[일상 예시]

1. 거스름돈 문제

| 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한개 존재합니다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러주어야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

이 문제의 해결 방법은 "가장 큰 단위의 돈부터 계산하자"임
단순히 돈을 돌려줄 수 있는 방법은 많지만, 동전의 최소 개수를 구해야하기 때문

위의 해결 절차를 적용한다면?

1. 선택 검사

• 현재 가장 비싼 돈을 선택

 

2. 적절성 검사

• 선택된 돈이 현재 남은 돈보다 큰지 확인
• 크다면 1번으로 돌아가 다음으로 비싼 돈 선택

 

3. 해답 검사

• 선택된 돈을 빼고, 여전히 돈이 남아있는지 확인
• 남아있다면 1번으로 돌아가 반복

answer = 0
change = [500, 100, 50, 10]
remain = money
for i in change:
    answer += remain//i
    remain = remain%i

---

[근사 알고리즘]

활용 조건을 만족하지 않는 경우, 근사 알고리즘을 적용할 수 있음

• 최적화 문제에 대한 답의 근사값을 구하는 알고리즘
• 가장 최적의 답을 구할 수는 없지만, 어느 정도 보장된 근사해를 계산할 수 있음
• 계산에 소요되는 시간이 비교적 빠름

---

관련 문제

백준 5585 : 거스름돈(브론즈2)

백준 14916 : 거스름돈(실버5)

---

[참고 자료]

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

탐욕법(그리디) 알고리즘

[알고리즘] 탐욕법(그리디) 알고리즘