탐욕법 (Greedy Algorithm)

매 선택에서 최적이라고 생각되는 결정을 내리면서 문제를 해결하는 알고리즘입니다.
즉, 전체 문제를 해결하기 위한 최적의 해답을 구하기 위해, 각 단계에서 가장 좋다고 생각되는 선택을 하여 '근사치를 추정'하는 방식입니다.
그리디 알고리즘은 항상 전체 문제에 대한 최적의 해를 보장하는 것은 아닙니다.

• 최적의 해 조건 1 : Greedy Choice Property
  앞의 선택이 이후의 선택에 영향을 주지 않을 경우

• 최적의 해 조건 2 : Optimal Substructure
  문제의 최적해가 작은 문제의 최적해로부터 구성되는 경우

<예시 : 동전 문제>

#include <iostream>

using namespace std;

int main() {
	int price = 3770; // 받야아 할 돈
	int coin[] = { 500, 100, 50, 10 }; // 잔돈 종류
	int change = 0; // 거스름돈의 수
	
	for (int i = 0; i < sizeof(coin) / sizeof(int); ++i) {
		while (price >= coin[i]) {
			price -= coin[i];
			++change;
		}
	}
	
	// 500원 7개, 100원 2개, 50원 1개, 10원 2개
	// 총 12개
	cout << change;

	return 0;
}

만약 350원 동전이 생긴다면?
최적 해: 500원 6개, 350원 2개, 100원 0개, 50원 1개, 10원 2개로 | total : 11개
실제 해 : 500원 7개, 350원 0개, 100원 2개, 50원 1개, 10원 2개 | total : 12개