그리디 알고리즘(탐욕법)
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
Author And Source
이 문제에 관하여(그리디 알고리즘(탐욕법)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dev_shu/그리디-알고리즘탐욕법저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)