[알고리즘] 3. 탐욕 알고리즘

in 알고리즘




1. 탐욕 알고리즘 (Greedy Algorithm)

  • 매 순간 최적 해를 선택하면서 최종적으로 최적해에 도달하는 알고리즘 설계 기법
  • 최적 부분 구조나 탐욕 선택 속성 문제를 해결하는데 적합
  • 매 순간 최적 해를 찾으면서 구하는 방법이 항상 최적임을 보장하지 않아 유의 필요
  • 동전 가지고 비교 설명할 때 자주 쓰인다.
  • 서울 - 대전 - 부산 가는 경로 시간 비교



2. 문제 - 거스름돈

잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 있고 언제나 거스름돈 개수가 가장 적게 잔돈을 준다.
타로가 잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

function solution(n){
    let coin = [500, 100, 50, 10, 5, 1]
    let answer = 0

    n = 1000 -n
    for (let i = 0; i<coin.length; i++){
        while(n >= coin[i]){
            n -= coin[i]
            answer++
        }
    }

    return answer
}

console.log(solution(380)) //4
console.log(solution(1)) //15



3. 문제 - 체육복

programmers 

function solution(n, lost, reserve) {
  let losted = [...lost].filter((x) => !reserve.includes(x));
  let reserved = [...reserve].filter((x) => !lost.includes(x));
  let answer = n - losted.length;

  let db = {};
  for (let i = 0; i < reserved.length; i++) {
    db[reserved[i]] = true;
  }

  losted = losted.sort((x, y) => x - y);
  for (let i = 0; i < losted.length; i++) {
    if (db[losted[i] - 1]) {
      answer++;
      db[losted[i] - 1] = false;
    } else if (db[losted[i] + 1]) {
      answer++;
      db[losted[i] + 1] = false;
    }
  }

  return answer;
}
  • 이중 for 문 사용을 줄이기 위해 객체로 key-value 활용하기
  • filter, includes 활용하기