Greedy Algorithm (탐욕 알고리즘)

알고리즘 문제를 푼다 = 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것

< Greedy Algorithm > 탐욕 알고리즘
-말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법.

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

# 특징
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
-탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.

---

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

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

이 과정을 통해 얻은 문제에 대한 해답은 다음과 같습니다.

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

# 적용 예시2

🥖$3 40g | 🍞$1.5 25g | 🥯$2.5 5g | 🥐 $2 20g

👜 LIMIT 35g

장발장이 빵 가게에서 빵을 훔치려고 합니다. 장발장의 가방은 35g까지의 빵만 담을 수 있고, 빵은 가격이 전부 다르며, 4개의 종류가 각 1개씩 있습니다. 빵은 쪼개어 담을 수 있습니다. 장발장은 최대한 가격이 많이 나가는 빵으로만 채우고 싶습니다.

장발장이 탐욕 알고리즘을 사용한다면 문제는 다음과 같이 간단해집니다.

1. 가방에 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣습니다.

2. 그다음으로 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣습니다.

3. 만약, 가방에 다 들어가지 않는다면 쪼개어 넣습니다.

달러당 부피가 가장 작은 빵(무게 대비 가장 비싼 물건)부터 담아야 합니다.

1. $1당 2g인 🥯 3번 빵(5g) 먼저 가방에 담을 수 있습니다: [남은 가방의 무게: 30g]
2. $1당 10g인 🥐 4번 빵(20g)을 다음으로 담을 수 있습니다: [남은 가방의 무게: 10g]
3. $1당 13.3g인 🥖1번 빵(40g)을 다음으로 담을 수 있습니다.
   1. 그러나, 40g을 온전히 못 채우기 때문에 쪼개어, 10g만 넣습니다: [남은 가방의 무게: 0g]

= $2.5 + $2 + $0.75 ⇒ 장발장은 최대 $5.25어치의 빵을 훔칠 수 있습니다.

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식입니다.

하지만, 만약 “빵을 쪼갤 수 없는 상황”이라면 마시멜로 실험 결과처럼 Greedy는 최적의 결과를 보장할 수 없습니다. 무게 대비 가장 비싼 물건을 넣는다는 조건을 두고 현재에 최선을 다하게 되면 빈 자리 5g이 남게 되고 결과를 도출하게 되지만, 빈 자리 5g을 채워 더 큰 최댓값을 만들 수 있는 최선의 상황이 있을 수도 있기 때문입니다.

마시멜로 실험이란?
지금 마시멜로를 받겠다고 말하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다.
greedy는 "현재"에 최선인 선택을 하기 때문에 마시멜로를 당장 받아내어 1개를 받게 되지만,
전체적으로 보게 되면 1분 뒤에 받는 2개가 최적의 선택이 된다.

따라서, 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못합니다. 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 합니다.

그 2가지가 특징이다.

---

출처

코드스테이츠