Greedy

1. Greedy란?

그리디는 직역하면 욕심쟁이라는 뜻으로 욕심쟁이 알고리즘이라고도 불린다.
그리디 알고리즘을 쉽게 정의하자면 매 순간 가장 최적의 선택을 하여 전체적인 최적해를 구하려는 방식의 알고리즘이다.
가장 대표적인 예시로는 동전 거스름돈이 존재한다.
500원, 100원, 50원, 10원의 거스름돈이 존재한다고 가정한다.
여기서 1000원을 내고 700원짜리 상품을 구매했을 때, 최소 개수의 동전으로 300원을 거슬러 주어야 한다.

1. 가장 큰 단위인 500원은 300원보다 크므로 사용할 수 없다.
2. 그다음으로 큰 100원을 사용하면 300원 중 100원이 차감되고, 남은 돈은 200원이다.
3. 다시 100원을 사용하여 남은 돈을 100원으로 줄인다.
4. 마지막으로 100원을 사용하면 거스름돈을 정확히 맞출 수 있다.

이 과정을 통해 100원 3개로 최소 개수의 동전을 사용하여 300원을 거슬러 줄 수 있다.

그러나 거스름 돈이 배수 형태가 아닌 10원, 7원, 1원이라고 생각해 보자
만약 14원을 거슬러 줄 때 동전을 몇 개를 줘야 할지 생각해 보자.
위 방법과 동일하게 가장 큰 값부터 거슬러준다면 10원, 1원, 1원, 1원, 1원으로 총 5개의 동전을 줄 것이다.
허나 14원은 7의 배수이므로 7원, 7원 2개를 거슬러 주는 게 제일 베스트다.

이처럼 그리디 알고리즘은 매 순간 최선의 선택을 하지만 항상 전체적으로 최적의 해를 보장하는 것은 아니다. 따라서 그리디 알고리즘을 올바르게 사용하기 위해서는 문제에 대한 명확한 분석과 증명이 필요하다.

2. 코드 (거스름 돈)

#include <bits/stdc++.h>
using namespace std;

int s[4] = {500, 100, 50, 10};
int price, pay, cnt, idx;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> price >> pay;
	
	int change = pay - price;
	
	while(change > 0)
	{
		if(change >= s[idx])
		{
			change -= s[idx];
			cnt++;
			cout << s[idx] << ' ';
		}
		else idx++;
	}
	
	cout << '\n' << cnt;
	
	return 0;
}

// 입력 결과
// 630 960
// 출력 결과
// 100 100 100 10 10 10 
// 6

3. 특징

1. 탐욕적 선택 속성 (Greedy Choice Property)
   각 단계에서 최적의 선택을 하면 전체적으로도 최적의 해가 보장되는 문제에 적용할 수 있다.
2. 최적 부분 구조 (Optimal Substructure)
   특정 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 한다.
3. 빠른 실행 속도
   일반적으로 O(N) 또는 O(N log N)의 시간 복잡도를 가지며, 다른 알고리즘보다 빠른 경우가 많다.

4. 마무리

명제를 세우고 증명을 하는것이 참 애매하고 어려운 듯하다.
수학적인 수식을 적용하고 증명하는 데에는 많은 시간이 필요하기 때문에 만약 코딩테스트나 이런 곳에서 그리디를 사용해야 한다면 정말 증명하고 풀 수 있을까라는 생각도 많이 든다. 이런 문제는 많이 풀면서 시간이 지나야 해결될 문제일 듯하다.