[Java] 그리디(Greedy) 알고리즘 개념 정리

그리디(Greedy) 알고리즘이란?

'탐욕스러운 알고리즘' : 나중을 생각하지 않고 지금 할 수 있는 최선의 선택을 한다.

특징

• 빠르다 : 모든 경우를 탐색하지 않음
• 항상 최적해를 보장하진 않음
• 특정 조건이 성립할 때만 사용 가능
  • 조건은 문제마다 다르며, 문제를 풀면서 감을 익혀야 함
  • ex) 동전 문제 : 큰 동전이 작은 동전의 배수 관계일 때 성립

---

예제 1) 동전 거스름돈

동전 {500, 100, 50, 10, 5, 1} 으로 1200원을 거슬러줄 때 최소 동전 개수를 구하라.

코드

public class GreedyPractice {
    static void main(String[] args) {
        int[] moneyList = {500, 100, 50, 10, 5, 1};
        int amount = 1200;
        int totalCount = 0;
        for (int money : moneyList) {
            int count = amount / money;
            if (count > 0) {
                System.out.println(money + "짜리 동전 X " + count + "개");
                totalCount += count;
                amount -= money * count;
            }
            if (amount == 0) break;
        }
        System.out.println("최소 동전 개수 : " + totalCount + "개");
    }
}

출력

500짜리 동전 X 2개
100짜리 동전 X 2개
최소 동전 개수 : 4개

동작 원리

내림차순으로 정렬된 동전 배열을 반복문으로 돌려 제일 큰 동전부터 선택한다.

int count = amount / money;  // 현재 동전으로 줄 수 있는 최대 개수

→ 1200 / 500 = 2개

totalCount += count;         // 총 개수에 더하기
amount -= money * count;     // 금액에서 빼기

→ totalCount = 2, amount = 1200 - 1000 = 200원 남음

다음 동전 100원이 들어오면

→ 200 / 100 = 2개
→ totalCount = 4, amount = 200 - 200 = 0원

if (amount == 0) break;      // 금액이 0이면 종료

→ 반복문 종료, 최소 동전 개수 4개 출력

---

예제 2) 최대 회의 수 구하기

문제 : 하나의 회의실에서 겹치지 않게 최대한 많은 회의를 열어라. 각 회의는 {시작 시간, 종료 시간} 으로 주어진다.

코드

int[][] meetings = {
        {1, 4}, {3, 5}, {0, 6}, {5, 9}, {3, 7},
        {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}
};

Arrays.sort(meetings, (a, b) -> a[1] - b[1]);

int count = 0;
int lastEnd = 0;
for (int[] meeting : meetings) {
    int start = meeting[0];
    int end = meeting[1];

    if (lastEnd <= start) {
        lastEnd = end;
        count += 1;
        System.out.println(count + "번째 회의! 시작 시간 : " + start + ", 끝 시간 : " + end);
    }
}
System.out.println("총 회의 수 : " + count);

출력

1번째 회의! 시작 시간 : 1, 끝 시간 : 4
2번째 회의! 시작 시간 : 5, 끝 시간 : 9
3번째 회의! 시작 시간 : 12, 끝 시간 : 16
총 회의 수 : 3

동작 원리

종료 시간이 짧을수록 새로운 회의를 더 많이 열 수 있으므로 종료 시간을 기준으로 오름차순 정렬한다.

Arrays.sort(meetings, (a, b) -> a[1] - b[1]);

a[1] - b[1] 의 반환값으로 정렬 방향을 결정한다.

• 양수 → 두 요소의 자리를 바꿈
• 음수 → 자리를 바꾸지 않음

a = 5, b = 6 → 5 - 6 = -1 (음수) → 자리 유지 → 오름차순
a = 6, b = 5 → 6 - 5 =  1 (양수) → 자리 바꿈 → 오름차순

그러므로 a[1] - b[1]는 어떤 값이 들어와도 항상 오름차순이 된다.
내림차순을 하고 싶으면 b[1] - a[1] 이와 같이 작성하면 된다.

정렬 후 반복문으로 종료 시간이 짧은 회의부터 가져온다.

if (lastEnd <= start) {
    lastEnd = end;
    count += 1;
}

이전 회의 종료 시간(lastEnd)과 현재 회의 시작 시간(start)을 비교해서 현재 회의 시작 시간이 같거나 늦다면 회의를 시작할 수 있으므로 count 를 1 증가시키고 lastEnd 를 현재 회의 종료 시간으로 갱신한다.

---

마무리

코드를 보고 선생님의 설명을 들을 때는 이해가 됐다고 생각했는데, 막상 문제만 놓고 혼자 풀어보려니 쉽지 않았다.
그리디는 단순히 코드를 외우는 게 아니라 문제마다 어떤 기준이 최선인지를 파악하는 게 핵심인 것 같다.
앞으로 문제를 많이 풀어보면서 감을 익혀야겠다. 💪