Greedy Algorithm
Greedy는 "탐욕스러운, 욕심 많은" 이란 뜻이다. Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법을 의미한다.
탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다.
Greedy Algorithm 문제 해결 단계
- 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한ㅁ다.
Greedy Algorithm 적용 예시
김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.
- 선택 절차(Selection Procedure) : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
- 적절성 검사(Feasibility Check) : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
- 해답 검사(Solution Check) : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복한다.
즉, 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 준다.
다른 예시로는 다음과 같다.
🥖$3 40g | 🍞$1.5 25g | 🥯$2.5 5g | 🥐 $2 20g
👜 LIMIT 35g
장발장이 빵 가게에서 빵을 훔치려고 합니다. 장발장의 가방은 35g까지의 빵만 담을 수 있고, 빵은 가격이 전부 다르며, 4 개의 종류가 각 1 개씩 있습니다. 빵은 쪼개어 담을 수 있습니다. 장발장은 최대한 가격이 많이 나가는 빵으로만 채우고 싶습니다.
장발장이 탐욕 알고리즘을 사용한다면 문제는 다음과 같이 간단해진다.
1. 가방에 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣는다.
2. 그다음으로 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣는다.
3. 만약, 가방에 다 들어가지 않는다면 쪼개어 넣는다.
1달러당 무게(반올림)
| 1달러당 무게(반올림) | |
|---|---|
| 🥖 | 13.3g |
| 🍞 | 16.7g |
| 🥯 | 2g |
| 🥐 | 10g |
달러당 부피가 가장 작은 빵(무게 대비 가장 비싼 물건)부터 담아야 한다.
- $1당 2g인 🥯 3번 빵(5g) 먼저 가방에 담는다:. [남은 가방의 무게: 30g]
- $1당 10g인 🥐 4번 빵(20g)을 다음으로 담는다. [남은 가방의 무게: 10g]
- $1당 13.3g인 🥖1번 빵(40g)을 다음으로 담는다. 그러나, 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가지 조건을 성립해야 한다.
탐욕 알고리즘의 특징
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.
