[알고리즘] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 최소한의 아이디어를 떠올릴 수 있는 능력 요구
• 정당성 분석이 중요
• 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토!
  - 그리디 알고리즘은 항상 최적의 해를 보장하지 않음.
• 최적 부분 구조 문제에서 사용

동전 거스름돈 문제

동전은 최적 부분 구조를 만족하기 때문에 그리디 알고리즘으로 해결할 수 있다.
제일 금액이 큰 동전은 금액이 작은 동전으로 만들어질 수 있기 때문이다.
제일 금액이 큰 500원을 사용하는 것부터 거스름돈을 계산하여 최적의 해를 구할 수 있다.

public class greedy {
	public static void main(String[] args) {
		int n = 입력금액;
		int cnt = 0;
		int[] coinTypes = { 500, 100, 50, 10 };

		for (int i = 0; i < 4; i++) {
			cnt += n / coinTypes[i];
			n = n % coinTypes[i];
		}
		System.out.println(cnt);
	}
}