그리디 알고리즘 (Greedy Algorithm)

🧭 그리디 알고리즘 (Greedy Algorithm)

📌 개념 요약

그리디 알고리즘은 매 단계에서 가장 최선의 선택을 하는 방식이다. 즉, 현재 상황에서 가장 좋아 보이는 선택을 하며, 이러한 선택들이 전체적으로도 최적의 해답을 이끌어낸다는 보장이 있을 때 사용된다.

알고리즘 흐름도

[시작]
   ↓
[문제와 입력값 정의]
   ↓
[현재 상황에서 최선의 선택]
   ↓
[선택이 전체 최적해로 이어지는가?]
   ↓
[선택을 저장하고 다음 단계로 이동]
   ↓
[모든 선택이 완료되었는가?]
   ↓
[최종 해답 출력]
   ↓
[종료]

예제: 동전 거스름돈 문제

문제 설명:

동전의 종류가 500원, 100원, 50원, 10원일 때, 거스름돈 1260원을 가장 적은 수의 동전으로 거슬러 주는 방법을 구하시오.

int[] coins = {500, 100, 50, 10};
int amount = 1260;			// 거스름돈
int count = 0;				// 거슬러줄 동전의 개수를 저장할 변수

for (int coin : coins) {
    count += amount / coin;	// 현재 동전으로 거슬러줄 수 있는 최대 개수만큼 더하기
    amount %= coin;			// 거스름돈에서 해당 동전 금액만큼 차감
}

System.out.println("동전 개수: " + count);

→ 가장 큰 단위의 동전부터 차례대로 거슬러 주는 방식으로, 각 단계에서 최선의 선택을 함으로써 전체적으로도 최적의 해답을 얻을 수 있다.