Greedy Algorithm(탐욕 알고리즘)

그리디 알고리즘(탐욕법, Greedy Algorithm)이란

• "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘이다
• 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다.

 

노드에서 가장 합이 높은 방법을 선택하는 방법은?

 

브루트 포스로 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 경우 또는 외판원 순회 문제 문서에 나와있는 복잡한 전략을 쓸수 도 있음.

일반적인 문제 해결

브루트 포스로 모두 살펴본 경우

 

그리디 알고리즘을 사용할경우

 

 

그리디 알고리즘의 특징

• 그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다.
• 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미

 

최적 부분 구조

 

서울에서 대구를 거쳐 부산까지 가는 최단 경로를 찾는다고 가정해보자.

서울에서 대구까지 가는 경로는 3가지, 부산까지도 3가지가 있다. 서울에서 대구까지 가는 최단 경로(200km)와 대구에서 부산까지 가는 최단 경로(80km)로 구성된다. 즉, 서울에서 대구를 거쳐 부산까지 가는 최단 경로는 각각의 부분 문제인 최단 경로 문제의 해결 방법의 합니다. 따라서 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다. 이러한 구조를 최적 부분 구조라 한다.

 

근사 알고리즘

그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 다만 어느 정도 적합한 수준의 해답을 알려준다. 따라서, 최적이 아닌 '되는가' 또는 ' 적당히 괜찮은 방법'을 찾을 때에는 사용할 수 있다. 특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기 때문에 실용적으로 활용하면서 사용이 가능하다

 

간단한 코딩 테스트 예제

1. 거스름돈 문제

가장 적은 수의 동전으로 거스롬돈을 줄 수 있는 방법을 구하라.(단, 동전은 무한히 있다)

function getChange(money) {
  const coins = [500, 100, 50, 10];
  let count = 0;

  for (let coin of coins) {
    count += Math.floor(money / coin);
    money %= coin;
  }

  return count;
}

// 예시
console.log(getChange(1260)); // 출력: 6

 

 

2. 회의실 배정 (활동 선택 문제)

N개의 회의가 주어졌을 때, 한 회의실에서 가장 많은 회의를 할 수 있는 최대 개수를 구하라.

(회의는 시작 시간과 끝나는 시간이 있음. 끝나는 시간이 빠른 순으로 정렬해서 그리디하게 선택)

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

  let count = 0;
  let endTime = 0;

  for (let [start, end] of meetings) {
    if (start >= endTime) {
      count++;
      endTime = end; // 다음 회의를 위해 endTime 업데이트
    }
  }

  return count;
}