•
그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구하는 알고리즘이다.
•
그리디 알고리즘을 사용하려면 문제가 아래의 조건을 만족해야 한다.
매 순간에서의 최선의 선택 = 문제에서의 최적해
•
그리디한 풀이가 가능한지 확인
◦
매 순간에서의 최선의 선택이 문제의 최적해와 일치하는지 확인
•
그리디한 풀이로 풀 수 없는 경우
◦
매 순간에서의 최선의 선택이 문제의 최적해와 일치하지 않는 경우에 해당
◦
브루트포스, DP, 수학과 같은 다른 방식의 접근이 필요함
BOJ_5585_거스름돈_JS
const coins = [500, 100, 50, 10, 5, 1];
function solution(input) {
let remain = 1000 - input;
let result = 0;
coins.forEach((coin) => {
if (coin <= remain) {
const q = Math.floor(remain / money);
result += q;
remain -= q * coin;
}
});
return result;
}
console.log(solution(380)); // 4
JavaScript
복사
Python
money = 1000 - int(input()) // input : 380
coins = [500, 100, 50, 10, 5, 1]
result = 0
for coin in coins:
cnt += money // coin
money %= coin
print(result) // 4
JavaScript
복사