[알고리즘 공부] 그리디(탐욕법)

---

그리디 (탐욕법)

---

현재 상황에서 가장 좋은 최적의 해 만 고르는 방법.
매 순간 최적의 해를 선택하며, 현재의 선택이 나중에 어떠한 영향을 미칠지는 고려하지 않는다.
문제를 여러 개의 부분 문제로 나누고, 각 부분 문제마다 답을 구해 결국 원하는 답을 구한다.
지금 이 순간 당장 최적인 것을 선택하는 알고리즘

그리디 알고리즘이 통하는 문제 유형

---

활동선택 문제

• 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우 찾기

• 물건을 구매할 때 지폐를 사용해서 금액에 맞게 지불한다. 금액이 주어지면 내야하는 지폐 개수의 최솟값을 구하기

탐욕법 성립 조건 2가지

1. 탐욕스러운 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않는 조건

2. 최적 부분 구조 조건 : 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결방법이다라는 조건
   이 성립되어야 잘 작동한다.

예제문제 1

그리디의 대표적인 문제

백준 - 회의실 배정 문제

const solution = (meeting) => {
  let answer = 0;

  meeting.sort((a, b) => {
    if (a[1] === b[1]) {
      // 끝나는 시간이 같으면
      return a[0] - b[0]; // 시작시간 기준으로 정렬
    } else {
      // 끝나는 시간이 다르면
      return a[1] - b[1];
    }
  });

  let endTime = 0;
  for (let x of meeting) {
    if (x[0] >= endTime) {
      answer++;
      endTime = x[1]; // 끝시간 맞춰주기
    }
  }
  return answer;
};

const meeting = [
  [1, 4],
  [3, 5],
  [0, 6],
  [5, 7],
  [3, 8],
  [5, 9],
  [6, 10],
  [8, 11],
  [8, 12],
  [2, 13],
  [12, 14],
];
console.log(solution(meeting));

참고