Greedy Algorithm Coplit

1.

// 박스에는 최대 2개의 짐만 넣을 수 있고 무게제한이 있음.
// 각각 들어가야 하는 짐의 무게들은 들쭉날쭉함.
// 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 리턴한다.
// 1 <= 옮겨야 할 짐의 개수 <= 50,000
// 40 <= 짐의 무게를 담은 배열 stuff <= 240
// 40 <= 박스의 무게 제한 limit <= 240

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

function movingStuff(stuff, limit) {
  // 2개의 짐이 모두 담겼을 때 카운팅하는 변수를 하나 선언한다
  let twoStuff = 0;
  
  // 짐을 담은 배열 stuff를 오름차순으로 정렬한다.
  // stuff가 [70, 50, 80, 50] 일 때, [80, 70, 50, 50]으로 정렬한다.
  let sortedStuff = stuff.sort((a, b) => a - b);
  
  // 가장 가벼운 무게를 가진 짐의 인덱스
  let lightIdx = 0;
  
  // 가장 무거운 무게를 가진 짐의 인덱스
  let heavyIdx = sortedStuff.length - 1;
  
  while(lightIdx < heavyIdx) {
    // 가장 가벼운 짐의 무게 + 가장 무거운 짐의 무게 <= limit이면
    // 2개의 짐을 한번에 나를 수 있다
    if(sortedStuff[lightIdx] + sortedStuff[heavyIdx] <= limit) {
      // 다음 짐을 확인하기 위해
      // 가장 가벼운 짐과 가장 무거운 짐의 인덱스를 옮기고
      // 한 번에 2개를 옮길 수 있는 개수 +1
      lightIdx++;
      heavyIdx--;
      twoStuff++;
    
    // 위의 조건과 맞지 않는 경우 === 한 번에 하나의 짐만 나를 수 있는 경우
    // 가장 무거운 짐의 인덱스만 옮긴다
    } else {
    heavyIdx--;
  }
  
  // 전체 짐의 개수에서 한 번에 2개를 나르는 경우를 뺀 것이 필요한 박스의 개수이다.
  return stuff.length - twoStuff;
}

 

// 이렇게 해도 테스트 케이스는 통과했지만
// 배열 메소드를 사용하여 푸는 것은 지양하는 편이 좋다

function movingStuff(stuff, limit) {
  let result = 0;
  let sortedStuff = stuff.sort((a, b) => a - b);
  
  while(stuff.length > 0) {
    if(sortedStuff[0] + sortedStuff[stuff.length - 1] <= limit) {
      stuff.shift();
    }
    stuff.pop();
    result++;
  }
  return result;
}

 

 

2. 

// [500, 100, 50, 10, 5, 1] --> 오름차순 정렬, 배수 관계
// 필요한 동전 개수의 최소값 리턴
// 1 <= 거스름돈 k <= 100,000,000

// 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 result = 0;

  let coin = [500, 100, 50, 10, 5, 1];

  for(let i = 0; i < coin.length; i++) {
    if(k > 0) {
      let sum = Math.floor(k / coin[i]);
      result += sum;
      k = k % coin[i];
    }
    return result;
  }
}

 

function partTimeJob(k) {
  // 동전의 개수
  let result = 0;

  let coins = [500, 100, 50, 10, 5, 1];

  for(let coin of coins) {
    // 소수점 자르기
    result += parseInt(k / coin)
    
    // 만약 4590원이면
    // 500원 9개로 4500원을 채우고
    // 90원은 다시 계산하는 방식으로
    k = k % coin
  }
  return result;
}

 

3.

// N * N의 크기를 가진 보드판(정사각형 모양의 보드판)
// 상하좌우(UDLR)로 움직일 수 있으며 조작의 기회는 한번만
// 좌표 왼쪽 상단에 말을 놓으며, 이는 항상 (0, 0)이다
// 한번 움직이면 한칸씩, 칸 안의 요소인 숫자 획득 가능
// 중복이 되어도 숫자 획득 가능, 칸 안의 숫자는 0 or 1
// 보드 바깥을 나간 말은 'OUT' 리턴

// board는 number타입의 2차원 배열
// 2 <= board.length <= 1,000
// operation은 string 타입의 대문자 영어가 쓰여진 문자열
// 1 <= operation.length <= board.length * 2
// UDLR 이외의 문자열은 없다고 한다

const board1 = [
  [0, 0, 0, 1],
  [1, 1, 1, 0],
  [1, 1, 0, 0],
  [0, 0, 0, 0]
]
const output1 = boardGame(board1, 'RRDLLD');
console.log(output1); // 4


const board2 = [
  [0, 0, 1],
  [1, 1, 1],
  [1, 0, 0]
]
const output2 = boardGame(board2, 'UUUDD');
console.log(output2); // 'OUT'

const board3 = [
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0]
]
const output3 = boardGame(board3, 'DDRRRUDUDUD');
console.log(output3); // 0

function boardGame(board, operation) {
  // 말이 움직이면서 획득하는 숫자의 합(점수)
  let score = 0;
  
  // 이동할 때 움직임을 저장하는 변수 x, y
  let x = 0;
  let y = 0;
  
  // 제일 처음 위치하는 좌측 상단의 좌표
  let curPoint = board[0][0];
  
  for(let i = 0; i < operation.length; i++) {
    if(operation[i] === 'U') y -= 1, x += 0;
    if(operation[i] === 'D') y += 1, x += 0;
    if(operation[i] === 'L') y += 0, x -= 1;
    if(operation[i] === 'R') y += 0, x += 1;

    // 만약 말이 보드를 이탈하면 'OUT'을 리턴한다
    if(y < 0 || board.length < y || x < 0 || board.length < x) return 'OUT';

    curPoint = board[y][x];

    // 숫자를 획득하는 경우
    score = score + curPoint;
  }
  return score;
}

 

function boardGame(board, operation) {
  // 세로
  let col = 0;
  
  // 가로
  let row = 0;
  
  // 결과(점수)
  let result = 0
  for(let i = 0;i<operation.length;i++){
    if(operation[i]==='U'){
      col--;
    }
    else if(operation[i]==='D'){
      col++;
    }
    else if(operation[i]==='L'){
      row--;
    }
    else if(operation[i]==='R'){
      row++;
    }
    
    // 예외인 경우
    else{
      continue;
    }
    
    if((col < 0 || col > board.length) || (row < 0||row > board.length)) return 'OUT'
    result += board[col][row]
  }
  return result
};

 

 

4. (DP) Advanced

let output = ocean(50, [10, 20, 50]);
console.log(output); // 4

let output = ocean(100, [10, 20, 50]);
console.log(output); // 10

let output = ocean(30, [5, 6, 7]);
console.log(output); // 4

function ocean(target, type) {
  // target을 훔칠 수 있는 방법의 수를 리턴한다.
  // 모든 화폐는 무한하게 있다고 가정한다.
  // target <= 100,000 자연수
  // type <= 100 자연수를 담은 배열

  // 어떠한 금액을 만들 수 있는 경우의 수를 기록하는 배열 bag을 하나 만든다.
  // bag[0] = 1
  let bag = [1];

  // 초기값을 0으로 만들어준다
  for(let i = 1; i <= target; i++) {
    bag[i] = 0;
  }

  // 돈의 종류가 담겨있는 배열을 순차적으로 탐색한다
  for(let i = 0; i < type.length; i++) {

    // target 금액까지 순차적으로 +1씩 증가
    for(let j = 0; j <= target; j++) {

      // bag의 인덱스가 type[i]보다 크거나 같은 경우
      // (작은 경우는 type[i]로 만들 수 있는 경우가 아니기 때문에 고려할 필요가 없음)
      if(type[i] <= j) {
        
        // 기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다.  
        bag[j] = bag[j] + bag[j - type[i]];
      }
    }
  }
  return bag[target];
}