그리디 알고리즘(탐욕법)

1.탐욕법

  • DP사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘
  • DP를 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념.
  • 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 부름.
  • 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법.
  • 이렇게 각 단계에서 최선의 선택한 것이 전체적으로도 최선이길 바라는 알고리즘.
  • 모든 경우에 다 적용되지 않음
  • 그리디 알고리즘이 통하는 몇몇 문제들(활동 선택, 분할가능 배낭)

2.활동 선택 문제

  • 한 강의실에서 여러 개의 수업을 할려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 것
  • i:교시 / S(i):시작시간 / f(i):종료시간
    i 1 2 3 4 5 6 7 8 9
    S(i) 1 2 4 1 5 8 9 11 13
    f(i) 3 5 7 8 9 10 11 14 16
  • 강의 시간이 겹치는 경우는 동시에 강의실 사용 불가
  • 위의 표대로 보면 A1, A3, A6, A8이나 A1, A3, A7, A9 등 가장 많이 수업을 할 수 있는 경우는 4개의 수업
  • DP로 통해 풀어 본다면, G1_8을 A1이 종료된 후부터 A8이 시작하기 전 활동들의 집합이라고 하면, G1_8 ={A3,A5,A6,A7}이며, 이중에서 최적의 조합 B1_8 = {A3,A6} 혹은 {A3,A7}
  • B1_8에서 A6을 골랐다고 하면, 거기서 두 개로 쪼개짐.
  • B1_6과 B1_8의 개수와 A6 1개를 더하면 최적 활동의 개수를 알 수 있음.
  • C[i,j] = max(C[i,k]+C[k,j]+1)
  • 하지만 동적 프로그램 사용시 모든 경우의 수를 구해야 함
  • 탐욕알고리즘의 경우 최적의 해를 구하기 위해서는 첫번째 활동이
    최대한 일찍 끝나면 됨. 그래야 다른 활동들을 더 많이 선택할 수 있기 때문.
function activitySelection(act) {
  let result = [];
  const sorted = act.sort(function(prev, cur) {
    return prev[2] - cur[2]; // 종료 시간 순으로 정렬 [활동번호,시작시간,종료시간]
  });
  let last = 0;
  sorted.forEach(function(item) {
    if (last < item[1]) { // 조건 만족 시 결과 집합에 추가
      last = item[2];
      result.push(item);
    }
  });
  return result.map(function(r) {
    return r[0]; // 어떤 활동들이 선택되었는지 새로운 배열로 생성해서 배열 리턴
  });
}
let 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]];
let output = activitySelection(activity);
console.log(output);

3. 분할 가능 배낭 문제

  • 무게가 초과할 것 같으면 물건을 쪼개서 일부만 넣을 수 있다.
    i 1 2 3
    v(i) 60 100 120
    w(i) 10 20 30
    v(i)/w(i) 6 5 4
  • 무게 대비 가치가 높은 것을 먼저 놓는 게 최선.
  • 무게 제한은 50
  • 3번째 물건은 물건 초과가 되서 20만큼 쪼개서 넣으면 됨.
let test = [[1,60,10], [2,100,20], [3,120,30]];
function fractionalKnapsack(item, w) {
  let sorted = item.sort(function(prev, cur) {
    return cur[1] / cur[2] - prev[1] / prev[2]; // 무게 대비 가치 순으로 정렬
  });
  let limit = w;
  let result = 0;
  for (let i = 0; i < sorted.length; i++) {
    let cur = sorted[i];
    if (limit > 0) {
      if (limit >= cur[2]) { // 물건 무게가 제한 이하일 경우
        limit -= cur[2];
        result += cur[1];
      } else { // 물건 무게가 제한 초과일 경우
        result += cur[1] / cur[2] * limit; // 잘라서 넣음
        limit = 0;
      }
    } else {
      break;
    }
  }
  return result;
}
fractionalKnapsack(test, 50); // 240

좋은 웹페이지 즐겨찾기