[Javascript로 정리하는 이코테] 1. 그리디 (Greedy)

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

개념

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
• 기준에 따라 좋은 것을 선택하는 알고리즘
• 해법이 정당한지 검증이 필요

 

💡 문제를 만났는데 바로 문제 유형을 파악할 수 없는 경우

1. 그리디 알고리즘을 의심하고 해법을 고민
2. 그리디로 해결할 수 없다면 → 다이나믹 프로그래밍이나 그래프 알고리즘으로 해결할 수 있는지 고민

 

예제 3-1. 거스름돈

const COIN_TYPES = [500, 100, 50, 10];

let n = 1260;
let count = 0;

for(const coin of COIN_TYPES){
  count += ~~(n / coin);
  n %= coin;
}

console.log(count);

 

 

실전 문제

큰 수의 법칙

입력 정제: 입력 조건에 모든 값이 자연수이므로, 숫자로 타입을 변환해야 한다.

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim().split('\n');

let [nums, arr] = input;
let [n, m, k] = nums.split(' ').map(v => +v);
arr = arr.split(' ').map(v => +v);

 

방법 1. 단순하게 풀기 (while) → O(m) = O(10,000)

function solution(n, m, k, arr){
  arr.sort((a, b) => b - a);
  const first = arr[0];
  const second = arr[1];
  
  let result = 0;
  while(1){
    if(m === 0) break;
    
    result += first * k;
    m -= k;
  
    result += second;
    m--;
  }
  
  return result;
}

console.log(solution(n, m, k, arr));

 

방법 2. 단순하게 풀기 (for)

function solution(n, m, k, arr){
  arr.sort((a, b) => b - a);
  const first = arr[0];
  const second = arr[1];
  
  let result = 0;
  for(let i = 0, tmp = 0; i < m; i++){
    if(tmp === k){
      result += second;
      tmp = 0;
    } else{
      result += first;
      tmp++; 
    }
  }
  return result;
}

 

방법 3. 수학적 아이디어 활용 방식 (반복되는 순열) → O(1)

function solution(n, m, k, arr){
  arr.sort((a, b) => b - a);
  const first = arr[0];
  const second = arr[1];

  //가장 큰 수가 더해지는 횟수
  let count = ~~(m / (k + 1)) * k;
  count += m % (k + 1);

  let result = 0;
  result += count * first;
  result += (m - count) * second;
  
  return result;
}

 

 

숫자 카드 게임

O(nm) = O(100*100)

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim().split('\n');

let [nm, ...arr] = input;
let [n, m] = nm.split(' ').map(v => +v);
arr = arr.map(v => v.split(' ').map(v => +v));

function solution(n, m, arr){
  let result = 0;
  for(const cur of arr){
    result = Math.max(result, Math.min(...cur))
  }
  return result;
}

console.log(solution(n, m, arr));

 

 

1이 될 때까지

O(n) <= O(100,000)

const fs = require('fs');
let input = fs.readFileSync("./tc.txt").toString().trim();

let [n, k] = input.split(' ').map(v => +v);

function solution(n, k){
  let result = 0;
  
  while(n > 1){
    if(n % k === 0){
      n /= k;
    } else{
      n--;
    }
    result++;
  }
  
  return result;
}

console.log(solution(n, k));