[알고리즘] greedy(그리디) 알고리즘

🥳 그리디 알고리즘

Greedy 알고리즘은 말 그래도 선택의 순간마다 눈앞에 보이는 최적의 상황만을 선택해 최종적인 해답에 도달하는 방법이다.

최적해를 구하는데에 사용되는 근사적인 방법이다.

순간마다 하는 선택은 그 순간에 대해 지역적으로 최적이지만, 최종적(전역적)인 해답을 만들었다고 해서 그것이 최적이라는 보장이 없다.

하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

🚦 그리디 알고리즘을 적용하기 위한 조건

1. 탐욕스러운 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

두 조건이 성립하지 않는 경우에는 그리디 알고리즘은 최적해를 찾지 못한다.

📖 그리디 알고리즘 문제

백준 11047: 동전0

문제 링크

만약 동전의 종류는 3개 1, 5, 10이고 59원을 만드는데 필요한 동전 개수는

10원짜리 5개, 5원짜리 1개, 1원짜리 4개로 총 10개가 필요하다

이처럼 큰 수부터 생각을 하면 쉽게 구할 수 있다.

아래코드는 자바스크립트로 작성하였다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const n = input[0].split(" ")[0];
const m = input[0].split(" ")[1];
const arr = input.slice(1).map((v) => Number(v));
let answer = 0;
let k = m;
for (let i = n - 1; i >= 0; i--) {
  if (k >= arr[i]) {
    const tmp = Math.floor(k / arr[i]);
    k -= tmp * arr[i];
    answer += tmp;
  }
}

console.log(+answer);