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

💡 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은 ‘탐욕법’ 또는 ‘욕심쟁이 알고리즘’이라고도 한다. 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

그리디 알고리즘은 각 단계에서 최적이라고 생각되는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘의 특징

• 매 순간 최적이라고 생각되는 선택을 한다.
• 한번 선택한 것은 번복하지 않는다.
• 항상 최적의 해를 보장하지는 않는다.

---

⚡ 그리디 알고리즘의 조건

그리디 알고리즘으로 문제를 해결하기 위해서는 다음 두 가지 조건을 만족해야 한다.

1. 탐욕적 선택 속성

   • 지역적으로 최적이면서 전역적으로도 최적인 선택이어야 한다.
   • 현재의 선택이 이후의 선택에 영향을 주지 않아야 한다.

2. 최적 부분 구조

   • 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되어야 한다.

---

🌟 그리디 알고리즘의 대표적인 예제

1. 거스름돈 문제

가장 대표적인 그리디 알고리즘 문제이다.
거스름돈을 줄 때 가장 적은 수의 동전을 사용하는 문제이다.

1. 큰 단위부터 차례대로 선택: 500원, 100원, 50원, 10원 동전 순으로 거슬러준다.
2. 500원부터 시작하여 거슬러주고, 그 후 남은 금액에 대해 100원, 50원, 10원 동전 순으로 처리한다.
3. 각 동전이 선택될 때마다 남은 금액을 업데이트하며, 최소 동전 개수를 계산한다.

function getMinCoins(change) {
  const coins = [500, 100, 50, 10]; // 동전의 종류
  let count = 0;

  for (let coin of coins) {
    count += Math.floor(change / coin); // 현재 동전으로 거슬러 줄 수 있는 개수
    change %= coin; // 남은 거스름돈 계산
  }

  return count;
}

console.log(getMinCoins(1260)); // 결과: 6

이 문제가 그리디로 해결되는 이유:

• 큰 단위가 작은 단위의 배수이므로, 작은 단위의 동전을 여러 개 사용하는 것보다 큰 단위의 동전을 사용하는 것이 항상 유리하다.
• 따라서 가장 큰 화폐 단위부터 차례대로 거슬러 주는 것이 최적의 해를 보장한다.

2. 회의실 배정 문제

시작 시간과 종료 시간이 주어질 때, 한 회의실에서 최대한 많은 회의를 진행하는 문제이다.

1. 종료 시간 기준으로 정렬: 회의들을 종료 시간이 빠른 순서대로 정렬한다. 종료 시간이 빠른 회의를 먼저 선택하면, 이후 회의를 선택할 수 있는 시간이 더 많아진다.
2. 회의 선택: 현재 회의의 시작 시간이 이전 회의의 종료 시간 이후에 시작되는 경우만 선택한다.
3. 최적의 회의 선택: 선택된 회의의 종료 시간을 갱신하고, 가능한 한 많은 회의를 선택하여 최적해를 구한다.

function maxMeetings(meetings) {
  // 종료 시간을 기준으로 정렬
  meetings.sort((a, b) => a[1] - b[1]);

  let count = 0;
  let endTime = 0;

  for (let meeting of meetings) {
    if (meeting[0] >= endTime) {
      // 시작 시간이 이전 회의 종료 시간보다 크거나 같으면
      count++;
      endTime = meeting[1];
    }
  }

  return count;
}

const meetings = [
  [1, 4],
  [3, 5],
  [0, 6],
  [5, 7],
  [3, 8],
  [5, 9],
  [6, 10],
  [8, 11],
  [8, 12],
  [2, 13],
  [12, 14],
];

console.log(maxMeetings(meetings)); // 결과: 4

이 문제가 그리디로 해결되는 이유:

• 종료 시간이 빠른 회의를 선택하는 것이 이후에 더 많은 회의를 선택할 수 있는 가능성을 높인다.
• 현재 선택한 회의가 끝난 후 가장 빨리 시작할 수 있는 회의를 선택하는 것이 최적해를 보장한다.

---

⚠️ 그리디 알고리즘의 한계

그리디 알고리즘은 항상 최적의 해를 보장하지는 않는다.

1. 동전 거스름돈 문제에서

   • 동전의 단위가 [500, 400, 100]이고 거스름돈이 800원이라면
   • 그리디: 500 + 100 + 100 + 100 (4개)
   • 최적해: 400 + 400 (2개)

2. 최단 경로 문제에서

   • 매 순간 가장 가까운 정점을 선택하는 방식으로는 최단 경로를 찾지 못할 수 있다.
   • 이런 경우 다익스트라 알고리즘과 같은 다른 방법을 사용해야 한다.

3. 배낭 문제에서

   • 물건을 분할할 수 없는 0/1 배낭 문제의 경우, 가치/무게 비율이 높은 것부터 선택하는 그리디 방식으로는 최적해를 찾을 수 없다.
   • 이런 경우 동적 프로그래밍으로 해결해야 한다.

---

🎯 문제 풀이 전략

그리디 알고리즘으로 문제를 해결할 때는:

1. 그리디로 해결이 가능한지 검토한다.
   • 현재의 선택이 이후의 선택에 영향을 주지 않는지
   • 부분 문제의 최적해가 전체 문제의 최적해인지
2. 정렬을 활용한다.
   • 대부분의 그리디 문제는 정렬과 함께 사용된다.
   • 정렬 기준을 잘 설정하는 것이 중요하다.
3. 반례를 찾아본다.
   • 그리디로 해결했을 때 반례가 없는지 확인한다.
   • 작은 크기의 입력값으로 테스트해본다.