그리디 알고리즘

그리디 알고리즘

패스트 캠퍼스 코딩 테스트 강좌 내 잔재미코딩 님의 부분을 참고했습니다.

정의

• Greedy algorithm 혹은 탐욕 알고리즘
• 최적의 해에 가까운 값을 구하기 위해 사용된다.
• 여러 경우 중 하나를 결정해야 할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구한다.

예제 1

지불해야하는 값이 4720원일 때, 1원, 50원, 100원, 500원 동전을 이용하여 지불하되, 가장 적은 수의 동전을 사용하시오.

접근

가장 가치가 큰 동전부터 사용해야 가장 적은 수의 동전을 사용하게 된다.

// 사용 가능한 동전을 담은 배열
const coins = [1, 50, 100, 500];

// @params : cost - 지불해야할 금액
// @params : coins - 사용할 동전을 담은 배열
const useMinCoins = (cost, coins) => {
  let totalUseCounts = 0; // 사용된 동전의 총 개수
  coins.sort((a, b) => b - a); // 가장 금액이 큰 동전부터 사용하기 위해 내림 차순 정렬
  // 지불해야 할 금액을 모두 지불할 때까지 반복
  for (let coin of coins) {
    if (cost >= 0) {
      const useCounts = Math.floor(cost / coin); // 지불금액을 현재 동전값으로 나눠 사용된 개수를 구한다. 소수점은 버린다.
      totalUseCounts += useCounts; // 총 동전 사용 회수에 해당 동전 사용 회수 추가.
      cost -= coin * useCounts; // 지불할 금액에서 해당 동전*사용회수 값만큼 뺀다.
    } else {
      // 지불할 금액이 없으면 반복문 종료;
      break;
    }
  }

  return totalUseCounts;
};

console.log(useMinCoins(4720, coins)); // 31 출력

Array.prototype.sort()

MDN Document 참고

arr.sort((a, b) => a - b); // 오름차순 정렬
arr.sort((a, b) => b - a); // 내림차순 정렬

예제 2

무게 제한이 k인 배낭이 최대한 가치 있도록 물건을 집어 넣자.

각 물건은 무게(w)와 가치(v)로 표현할 수 있다.

물건은 쪼갤 수 있고, 물건의 일부분을 배낭에 넣을 수 있다. (Fractional Knapsack Problem)

Fractional Knapsack Problem과 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제는 0/1 Knapsack Problem이라고 부른다.

물건(i)	item1	item2	item 3	item4	item5
무게(w)	10	15	20	25	30
가치(v)	10	12	10	8	5

구현

// 물건 배열. [무게, 가치]
const items = [
  [10, 10],
  [15, 12],
  [20, 10],
  [25, 8],
  [30, 5]
];

// @params: items - 물건이 담긴 배열
// @params: capacity - 가방의 최대 하중
const getMaxValue = (items, capacity) => {
  let totalValue = 0; // 가방의 총 가치

  items.sort((a, b) => {
    // 나눠서 담을 수 있으므로 무게 당 가치를 구한다.
    const valuePerWeightOfA = a[1] / a[0];
    const valuePerWeightOfB = b[1] / b[0];
    // 값이 가장 큰 물건부터 집어넣기 위해 내림차순 정렬.
    valuePerWeightOfB - valuePerWeightOfA;
  });

  for (let item of items) {
    // 배낭이 해당 물건을 온전히 담을 수 있을 때
    if (capacity - item[0] >= 0) {
      capacity -= item[0]; // 최대 하중에서 물건의 무게만큼 뺸다.
      totalValue += item[1]; // 배낭의 가치에 물건의 가치만큼 더한다.
    } else {
      const fraction = capacity / item[0]; // 남은 하중에 item의 일부가 얼마나 들어가는지 계산
      totalValue += fraction * item[1]; // 해당 물건의 일부분 * 가치
      // 최대하중에서 물건의 무게를 뺀 값이 0 미만이라면
      // 해당 물건을 넣으면 최대하중이 가득 찬다는 뜻이므로 반복 종료
      break;
    }
  }

  return totalValue;
};

console.log(getMaxValue(items, 30)); // 24.5 출력

한계

탐욕 알고리즘은 최적의 해를 반드시 구하는 것은 아니기 때문에 근사치 추정에 활용된다.