그리디 알고리즘

그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.

동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다.

그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불린다.

미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다.

이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.

물론 모든 경우에서 그리디 알고리즘이 통하지는 않으며, 쉬운 예를 들자면 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다가 선택하면 2개의 마시멜로를 받는 문제에서는, 그리디 알고리즘을 사용하면 항상 마시멜로를 한개밖에 받지 못한다. 지금 당장 최선의 선택은 마시멜로 1개를 받는 거지만, 결과적으로는 1분 기다렸다가 2개를 받는게 최선이기 때문이다.

활동 선택 문제 #

활동 선택 문제는 쉽게 말하면 한 강의실에서 여러 개의 수업을 하려고 할 때 한번에 가장 많은 수업을 할 수 있는 경우를 고르는 것이다.

아래에서 Si는 시작시간, Fi는 종료시간이다.

같은 강의실을 사용해야 하므로 A1과 A4는 동시에 선택할 수 없다.

A1, A2도 시간이 겹치므로 선택할 수 없다.

그렇지만 A1, A3는 선택할 수 있다. 이렇게 선택하여 가장 많은 수업을 할 수 있는 경우를 찾는 것이다.

결과적으로 a1, a3, a6, a8 or a1, a3, a7, a9 등을 고르면 정답이다. 문제는 이것을 어떻게 컴퓨터에게 고르도록 시키느냐 겠다.

DP 방식을 사용해서 문제를 풀 수 있지만 모든 C들을 구해야 하므로 그리디 알고리즘방식을 사용한다면 더욱 효율적으로 풀 수 있다.

문제 풀이 #

직관적으로 생각하면, 최적의 해를 구하기 위해서는 첫 번째 활동이 최대한 일찍 끝나면 된다.

그래야 다른 활동들을 더 많이 선택할 수 있기 때문이다. 위의 경우세ㅓ는 첫 선택으로 가장 빨리 끝나는 A1을 골라야하며 골랐다면 이제 A2, A4는 고를 수 없다.

그 다음 선택은 다음으로 일찍 끝나는 A3가 된다. 그 다음은 A6, A8 이 되어 최종적으로 A1, A3, A6, A8이 된다.

var activity = [[1,1,3], [2,2,5], [3,4,7], [4,1,8], [5,5,9], [6,8,10], [7,9,11], [8,11,14], [9,13,16]];
function activitySelection(act) {
  var result = [];
  var sorted = act.sort(function(prev, cur) {
    return prev[2] - cur[2]; // 끝나는 시간 순으로 정렬
  });
  var last = 0;
  sorted.forEach(function(item) {
    if (last < item[1]) { // 조건 만족 시 결과 집합에 추가
      last = item[2];
      result.push(item);
    }
  });
  return result.map(function(r) {
    return r[0]; // map을 한 이유는 그냥 몇 번째 행동이 선택되었는지 보여주기 위함.
  });
}
activitySelection(activity); // [1, 3, 6, 8]