Greedy Algorithm
"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"
Q . 마시멜로 실험 (마시멜로 1개를 주고, 먹지 않고 기다리면, 2개를 주는 실험)에 그리디 알고리즘을 사용한 결과는 무엇일까 ?
A . 눈 앞의 마시멜로를 당장 먹는다.
하지만, 기다렸다 2개를 먹는 최적해를 보장해주지 못한다.
☞ 그리디 알고리즘을 사용해야 하는 상황을 잘 판단해야 한다.
Greedy 알고리즘 사용하는 문제
- 최적 부분 구조와 탐욕 선택 속성의 특징을 가진 문제들
= 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다.
대표적인 예시 : 거스름돈 문제
동전 500원, 100원, 50원, 10원의 동전이 무한개 존재합니다. N원을 거슬러 줄 때, 필요한 동전의 최소 개수는 몇개인지 구하라.
"무조건 큰 화폐 단위부터 거슬러 준다" 는 알고리즘만 지키면 최적의 해를 항상 보장할 수 있다.
[예시 코드 / C++]
#include<bits/stdc++.h>
using namespace std;
int N, ans;
int main() {
int coins[4] = { 500,100,50,10 };
cin >> N;
for (int i = 0; i < 4; i++) {
cout << coins[i] << "원: " << N / coins[i] << "개\n";
ans += N / coins[i];
N %= coins[i];
}
cout <<"총 "<< ans << "개";
return 0;
}
참조 사이트
https://blog.naver.com/ndb796/221242106787
https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
☁️