Greedy Algorithm

기본적인 절차

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다.
탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있습니다.

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.

예제)
김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택합니다.
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사합니다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택합니다.
3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사합니다. 액수가 부족하면 1번 과정부터 다시 반복합니다.

이 과정을 통해 얻은 문제에 대한 해답은 다음과 같습니다.
가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 줍니다.

탐욕 알고리즘은
최적이라 생각되는 해답(locally optimal solution)을 찾으며,
이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식입니다.
그러나 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 합니다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.

코플릿 문제

Q1) 짐나르기 문제
김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.

예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.

박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.

짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

입출력예시

let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3

let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4

코드

let count = 0;
  let sort = stuff.sort(function(a, b) {
    return a - b;
  });

  while(sort.length !== 0){
   if(sort[0] + sort[sort.length - 1] <= limit){
       sort.shift();
       sort.pop();
        count++;
      }else{
        sort.pop();
        count++;
      }
  }

Reference Code

function movingStuff(stuff, limit) {
  let twoStuff = 0;
  // 짐을 무게순으로 오름차순 정렬
  let sortedStuff = stuff.sort((a, b) => a - b);
  // 가장 가벼운 짐의 인덱스
  let leftIdx = 0;
  // 가장 무거운 짐의 인덱스
  let rightIdx = sortedStuff.length - 1;
  while(leftIdx < rightIdx) {
      // 가장 가벼운 짐과 무거운 짐의 합이 limit 보다 작거나 같으면 2개를 한번에 나를 수 있다
      if(sortedStuff[leftIdx] + sortedStuff[rightIdx] <= limit) {
      // 다음 짐을 확인하기 위해 가장 가벼운 짐과 무거운 짐을 가리키는 인덱스를 옮겨주고
      // 한번에 2개 옮길 수 있는 개수를 +1 해준다   
          leftIdx++;
          rightIdx--;
          twoStuff++;
      } else {
          // 위 조건에 맞지 않는 경우는 한번에 한 개만 나를 수 있는 경우이기 때문에
          // 가장 무거운 짐의 인덱스만 옮겨준다
              rightIdx--;
      }
  }
  // 전체 짐의 개수에서 한번에 2개를 나를 수 있는 경우를 빼 주면 총 필요한 박스의 개수를 구할 수 있다
  return stuff.length - twoStuff;
}

Q2) 편의점 알바
편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었습니다.
현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

입출력예시

// 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다.
const output1 = test1(4000);
console.log(output1); // --> 8

// 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개, 50원짜리 동전 1개, 10원짜리 동전 2개, 1원짜리 동전 2개, 총 18개를 반환합니다.
const output2 = test1(4972);
console.log(output2); // --> 18

코드

function partTimeJob(k) {
  let count = 0;
  const coin = [500, 100, 50, 10, 5, 1]
  // 최소한의 동전으로 거스름돈을 주는 방법 === 가장 큰 동전을 우선 주는 식으로 하는게 best다 !!
  // 4100 원이라고 하면 500원을 8개주고 100원을 하나 주고
  for(let i=0; i<coin.length; i++){
    count += Math.floor(k/coin[i]);  
    k = k - coin[i]*Math.floor(k/coin[i]);
  }
  return count;
  // TODO: 여기에 코드를 작성하세요.
}
// 가장 큰수로 우선 나눠서 k를 가정적은 카운트로 작게 만드는거 !! 
// 작게 만든 나머지를 가지고 또 반복문을 돌려서 두번째 큰수로 나눠줒는것

Reference Code

function partTimeJob(k) {
  let result = 0;
  const wallet = [500, 100, 50, 10, 5, 1];
  for(let i = 0; i < wallet.length; i++) {
    if(k > 0) {
      const sum = Math.floor(k / wallet[i]);
      result += sum;
      k = k - (wallet[i] * sum);
    }
  }
  return result;
}