Greedy(그리디) 란?
- 매 선택에서 현재 당장 최적인 답 을 선택해 전체 적합한 결과를 도출하는 기법
- BackTracking을 통해 추가 점검을 하지 않고 현재 조건에서 선택했다면, 더이상 다른 선택 가능 경우는 검증하지 않는다.
- 지역적으로 최적이면서 전역적으로 최적인 문제들에 적용한다.
한계점
- 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 전체에서 최적이라는 보장은 없다.
Greedy 알고리즘 문제 해결 방법
1. 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사 (Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사 (Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 과정을 반복함
Greedy 알고리즘 조건
탐욕스러운 선택 조건
- 앞의 선택이 이후에 선택에 영향을 주지 않는다
- 항상 안전하다는 것이 보장되어야 한다.
- 전체 문제의 최적해를 반드시 도출할 수 있어야 한다.
최적 부분 구조 조건
- 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다.
-
전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출되어야 한다
예시
-
그리디 알고리즘 : 시작 지점부터 가장 큰 수를 얻는 path, 17을 선택
결론적으로 그리디 알고리즘은 시작 - 17 - 23 path가 가장 좋은 것이라고 판단함
→ 이때 6 아래의 128이라는 값이 있어서 Path를 변경할 수 없다
결론
Greedy 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
이 장점으로 인해 Greedy 알고리즘은 근사 알고리즘으로 사용할 수 있다.
Greedy 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 Greedy 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다.
그래서 실용적으로 사용할 수 있다.
예시 코드
거스름돈
// greedy algorithm (거스름 돈 문제)
// 10000 5000 1000 500 100 50 10
function getChange(value) {
let changes = [10000, 5000, 1000, 500, 100, 50, 10];
let won = Math.floor(value / 10) * 10; // 1의 자리 원화 반내림
let i = 0;
let counts = [];
while (true) {
if (won >= changes[i]) {
let count = Math.floor(won / changes[i]);
won = won - changes[i] * count;
counts[i] = count;
} else {
counts[i] = 0;
}
i++;
if (won === 0) {
for (let j = 0; j < changes.length - i; j++) {
counts.push(0);
}
break;
}
}
changes.map((change, index) => {
console.log(`${change.toLocaleString()}원 ${counts[index]}개`);
});
}
getChange(32660);
/*
10,000원 3개
5,000원 0개
1,000원 2개
500원 1개
100원 1개
50원 1개
10원 1개
*/
getChange(1000);
/*
10,000원 0개
5,000원 0개
1,000원 1개
500원 0개
100원 0개
50원 0개
10원 0개
*/
getChange(1500);
/*
10,000원 0개
5,000원 0개
1,000원 1개
500원 1개
100원 0개
50원 0개
10원 0개
*/
FrontEnd Developer.