탐욕 알고리즘

탐욕 알고리즘

여러 경우 중 하나를 결정해야할때마다 그 순간에 최적인 것을 선택해나가는 방식으로 최종적인 해답에 도달한다. 순간마다 하는 선택은 지역적으로는 최적이지만 최종적인 해답이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

문제1

짐 나르기

김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.
예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.
박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.
짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

풀이1

function movingStuff(stuff, limit) {
  stuff.sort((a,b) => b-a); //내림차순 정렬
  let box = 0;
  while(stuff.length) {
    box++;
    if(stuff[0]+stuff[stuff.length-1]<=limit) {
      stuff.pop();
    }
    stuff.shift();
  }
  return box;
}

풀이2

function movingStuff(stuff, limit) {
  stuff.sort((a,b) => a-b); //오름차순 정렬
  let leftIdx = 0;
  let rightIdx = stuff.length-1;
  let box = 0;
  
  while(leftIdx<rightIdx) {
    if(stuff[leftIdx]+stuff[rightIdx]<=limit) {
      leftIdx++;
      rightIdx--;
      box++
    } else {
      box++;
      rightIdx--;
    }
  }
  if(leftIdx===rightIdx) {
    box++
  }
  return box;
}  

문제2

편의점 알바

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

function partTimeJob(k) {
  const coins = [500, 100, 50, 10, 5, 1];
  let count = 0;
  
  for(const el of coins) {
    count += Math.floor(k/el);
    if(k%el === 0) return count;
    else {
      k = k-el*(Math.floor(k/el));
    }
  }
}