greedy algorithm

탐욕(greedy) 알고리즘

• 최적해를 구하는 데에 사용하는 근사적인 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행

Greedy algorithm의 과정

1. 가장 탐욕스러운 선택 (Make some greedy choice)
2. 문제를 조금 더 작은 문제로 분해(Reduce to a smaller subproblem)
3. 반복 (Iterate)

💡 Safe move

• Greedy choice 중 첫 번째로 선택한 것이 최적의 선택과 일치한 경우

1. Question 거스름돈 문제

- 지불 금액 5420원을 동전 모음(10원, 50원, 100원, 500원)으로 최소한의 동전 개수로 금액 지불

const cost = 5420;
const coins = [10, 50, 100, 500];
	
const costCtr = (cost, coins) => {
  let coinCount = 0;
  
  // 최소한의 동전갯수를 사용하기 위해 내림차순 정렬
  coins.sort((a, b) => b - a);
  
  for(const coin of coins) {
    if(coin >= 0) {
        const useCoin = Math.floor(cost/coin);
        cost -= useCoin * coin;
        coinCount += useCoin;
    }else {
      break;
    }
  } 
  return coinCount;
}

const result = costCtr(cost, coins);
console.log(result); // 16

2. Question 배낭 문제

• 물건과 그에 대한 가치가 주어지며, 가방의 최대 한도 무게가 주어졌을 때, 최대한 높은 가치의 물건을 담아라
  

const bagWeight = 15;
// 무게/가치 배열 생성
const items = [
  [12, 4],
  [2, 2],
  [1, 2],
  [1, 1],
  [4, 10]
]

const getItem = (bagWeight, items) => {
  let result = 0;

  // 무게별 가치가 큰 순서로 내림 차순
  items.sort((a, b) => b[1] / b[0] - a[1] / a[0]);

  for (const item of items) {
    // 가방 무게 - 아이템무게가 0보다 크거나 같다면 전부 담을 수 있음
    if (bagWeight - item[0] >= 0) {
      bagWeight -= item[0]; // 담은 무게 만큼 계산
      result += item[1]; // 가치 추가
    } else {
      // 가방에 남은 무게 계산하여 담을 수 있는 무게 측정
      const remainder = bagWeight / item[0];
      result += remainder * item[1]; // 가치 추가
      break; // 더 이상 담지 못함 -> for문을 빠져나옴
    }
  }
  return result;
};

console.log(getItem(bagWeight, items)); // 17.33333..