📌 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은
현재 상황에서 가장 최선이라고 생각되는 선택을 반복하는 알고리즘이다.

즉, 미래를 미리 고려하기보다
“지금 당장 가장 좋은 선택”을 계속 고르는 방식이다.

대표적으로는 다음과 같은 상황에서 사용된다.

동전 거스름돈 문제
회의실 배정 문제
최소 비용 계산 문제

1️⃣ 대표적인 문제

💰 거스름돈 문제

거스름돈이 1260원일 때
500원, 100원, 50원, 10원 동전을 사용하여
최소 개수의 동전으로 거슬러 주기

<풀이 핵심>
: 가장 큰 동전부터 최대한 사용한다.

int[] coins = {500, 100, 50, 10};
int money = 1260;
int count = 0;

for (int coin : coins) {
    count += money / coin;
    money %= coin;
}

System.out.println(count);

2️⃣ 그리디 알고리즘 문제 공식

그리디 문제를 보면 보통 아래 흐름으로 접근한다.

✅ STEP 1. 기준 정하기

무엇을 우선 선택할 것인가?

• 가장 큰 값
• 가장 작은 값
• 가장 빠른 시간
• 가장 적은 비용

✅ STEP 2. 정렬하기

그리디 문제는 대부분 정렬이 핵심이다.

Arrays.sort(arr); 혹은 Comparator를 사용해 기준 정렬을 한다.

✅ STEP 3. 현재 최선 선택 반복

반복문을 돌며 현재 기준에서 가장 좋은 선택을 계속 수행한다.

⚠️ 그리디 알고리즘의 함정
"현재 최선의 선택"이 "전체 최적의 선택"을 보장해야 한다.

예를 들어 특정 동전 구조에서는
큰 동전부터 선택하면 오히려 비효율적일 수 있다.

따라서 규칙성이 있는가?
현재 선택이 미래에도 영향을 주지 않는가? 를 확인해야 한다.

3️⃣ 그리디 알고리즘 문제

• 프로그래머스
  Greedy 문제 정리 사이트
  
• LeetCode
  LeetCode Greedy Problem List
  Greedy 문제 정리 사이트