탐욕스러운 알고리즘
- Greedy는 “탐욕, 탐욕”이라는 뜻으로, 말 그대로 선택의 순간마다 궁극적인 해답을 찾기 위해 눈앞의 최적의 상황을 따라가는 것입니다.
그리디 알고리즘은 다음과 같이 문제를 단계별로 해결합니다.
그리디 알고리즘 문제 해결 단계
- 선택 과정: 현재 상태에 대한 최적의 솔루션 선택
- 타당성 확인: 선택한 솔루션이 문제의 조건을 충족하는지 확인
- 솔루션 확인: 원래 문제가 해결되었는지 확인합니다. 그렇지 않은 경우 선택 과정으로 돌아가서 위의 과정을 반복하십시오.
그리디 알고리즘 적용 예시
이 탐욕스러운 알고리즘을 일반적인 경우에 적용합니까?
코딩김은 오늘도 편의점에서 열심히 일한다. 손님으로 온 박해커는 안주와 음료수를 챙겼고, 물품의 총 가격은 4,040원이었다. 해커는 계산에 5000원을 쓰고 최소한의 코인으로 거스름돈을 요구했다. 이 시점에서 Kim 인코딩을 어떻게 반전시켜야 합니까?
그리디 알고리즘으로 코인의 수를 세는 것은 우리가 일반적으로 변경할 코인을 선택하는 방법과 동일합니다. 960원 거스름돈을 충전하려면 먼저 500원 동전을 선택합니다. 다음으로 100원짜리 4개, 50원짜리 1개, 10원짜리 1개를 뽑는다. Greedy Algorithm 문제 해결 과정을 Kim Coding의 입장에 적용하면 다음과 같이 문제를 단계별로 나눌 수 있다.
- 선택 방법: 변경되는 코인의 수를 줄이기 위해 현재 가치가 가장 높은 코인을 먼저 선택합니다.
- 적정성 확인: 1단계에서 선택한 코인의 합이 반환 금액을 초과하는지 확인합니다.
- 정답 확인: 선택한 코인의 합이 반환 금액과 일치하는지 확인합니다. 양이 충분하지 않으면 1단계부터 반복하십시오.
이 과정을 통해 얻은 질문에 대한 답은 다음과 같다.
먼저 가장 가치가 높은 500원짜리 동전을 반납하고 잔고를 확인한다. 그리고 100원짜리 4개, 50원짜리 1개, 10원짜리 1개를 차례로 돌려준다.
마지막으로 하나의 예를 더 살펴보겠습니다.
$3 40g | $1.5 25g | $2.5 5g | $2 20g
한도 35g
장발장은 빵집에서 빵을 훔치려 한다. 장발장의 가방은 빵 35g까지만 담을 수 있고, 빵마다 가격이 다르며, 빵은 1개씩 4종류가 있습니다. 장발장은 최대한 비싼 빵으로 채우고자 합니다.
Valjean이 그리디 알고리즘을 사용하면 문제는 다음과 같이 단순화됩니다.
- 무게 기준으로 가장 비싼 물건을 가방에 넣으십시오.
- 다음으로 안에 넣을 수 있는 물건 중에서 무게가 가장 비싼 물건을 넣는다.
- 가방에 모두 들어가지 않으면 나누어서 보관하십시오.
달러당 무게(반올림)
| 13.3g | |
| 16.7g | |
| 2g | |
| 10g |
달러당 부피가 가장 작은 빵(무게 기준으로 가장 비싼 조각)을 먼저 적재해야 합니다.
- 빵 #3(5g), $1당 2g, 먼저 포장 가능: (남은 봉투의 무게: 30g)
- $1당 10g, 빵 #4(20g)에는 다음이 포함될 수 있습니다. (남은 봉지의 무게: 10g)
- 1달러당 13.3g의 빵 #1(40g)은 다음에 제공될 수 있습니다.
하지만 40g을 완전히 채울 수 없기 때문에 쪼개서 10g만 추가합니다. (남은 봉투 무게: 0g)
= $2.5 + $2 + $0.75 ⇒ Valjean은 최대 $5.25 상당의 빵을 훔칠 수 있습니다.
그리디 알고리즘은 문제 해결 과정의 매 순간 국부적으로 최적의 솔루션을 찾고, 이를 바탕으로 전역 최적 솔루션에 도달하는 문제 해결 방법입니다.
그러나 마시멜로 실험과 같이 “빵을 나눌 수 없는 경우” Greedy는 최적의 결과를 보장할 수 없습니다. 가장 비싼 물건을 무게로 놓는 조건으로 현재 시제에 최선을 다하면 5g의 빈 공간이 있고 결과가 그려집니다.
마시멜로 실험이란?
지금 마시멜로를 먹고 싶다고 하면 하나를 얻을 수 있지만, 그것을 얻기 위해 잠시 기다리면 두 개를 얻을 것입니다. Greedy는 “현재” 시간에 최선의 선택을 하기 때문에 즉시 마시멜로를 받고 하나를 얻지만 전체적으로는 1분 후에 받은 두 개가 최적의 선택입니다.
따라서 탐욕 알고리즘은 두 가지 조건이 충족되지 않는 한 최적의 솔루션을 보장하지 않습니다. 그리디 알고리즘을 적용하기 위해서는 풀고자 하는 문제가 다음 두 가지 조건을 만족해야 한다.
그리디 알고리즘의 특징
- 욕심 많은 선택 속성 이전의 선택은 후속 선택에 영향을 미치지 않습니다.
- 최적 하부 구조 문제에 대한 최종 솔루션은 하부 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
Greedy 알고리즘은 항상 최적의 결과를 제공하지는 않지만 합리적으로 최적에 가까운 값을 빠르게 도출할 수 있는 장점이 있습니다.