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

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