그리디(탐욕) 알고리즘

그리디 알고리즘

• 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.(동적 프로그래밍은 후에 기술 예정)
• 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다.
• 매 순간 최적의 해를 선택하며, 현재의 선택이 나중에 어떠한 영향을 미칠지는 고려하지 않는다.
• 문제를 여러개의 부분 문제로 나누고, 각 부분 문제마다 답을 구해 결국 원하는 답을 구한다.

그리디 알고리즘이 통하는 문제 유형

활동 선택 문제

• n개의 활동이 있을 때 최대한 많은 활동 수를 구하는 문제

  예시 문제) 한 회의실에서 여러 개의 미팅을 하려고 할 때 한 번에 가장 많은 미팅을 할 수 있는 경우 찾기

function solution(meeting) {
  let answer = 0;
  let sortMeeting = meeting.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    else return a[1] - b[1];
  });
  // 끝나는 시간으로 정렬
  // 끝나는 시간이 같다면 시작 시간으로
  let endTime = 0;
  for (let x of sortMeeting) {
    if (x[0] >= endTime) {
      answer++;
      endTime = x[1];
    }
  }

  return answer;
}

// 입력 예시
let arr = [
  [1, 4],
  [2, 3],
  [3, 5],
  [4, 6],
  [5, 7],
];

• 이 문제의 경우 직관적으로 생각하면 첫 번째 활동이 최대한 일찍 끝나면 된다.
• 미팅 끝나는 시간이 빠른 기준으로 정렬을 하면 수월 해진다.

  예시 문제) 거스름 돈

function solution(k) {
  let count = 0;
  const arr = [500, 100, 50, 10, 5, 1];
  for (let x of arr) {
    count += Math.floor(k / x);
    k = k - x * Math.floor(k / x);
  }
  return count;
}

• 이 문제도 직관적으로 생각하면 큰 지폐부터 내면 최소의 갯수를 구하기 쉬울 것이다.
• 값이 높은 지폐순으로 정렬을 하고 문제를 풀면 수월해진다.

분할 가능 문제

• 무게나 양이 주어지고 리미트를 줘서 제한을 두는 문제

  에시 문제) 집의 무게가 있고 옮길 수 있는 최대 무게가 있을 때, 몇번에 걸쳐서 옮길 수 있는지

let stuff = [70, 50, 80, 50];
let limit = 100;
function solution(stuff, limit) {
  let count = 0;
  let sortedStuff = stuff.sort((a, b) => a - b);

  while (sortedStuff.length !== 0) {
    if (sortedStuff[0] + sortedStuff[sortedStuff.length - 1] <= limit) {
      count++;
      sortedStuff.shift();
      sortedStuff.pop();
      // 가장 무거운 짐과 가장 가벼운 짐의 합이 한계치를 넘지 않으면
      // 그 둘을 같이 옮긴다. 그래서 각각 shift, pop 한 것.
    } else {
      count++;
      sortedStuff.pop();
      // 한계치를 넘으면 무거운 것만 옮긴다.
    }
  }
  return count;
}

예시 문제) 프로그래머스 구명보트

function solution(people, limit) {
  let answer = 0;
  people.sort((a, b) => a - b);
  let lt = 0;
  let rt = people.length - 1;
  while (lt <= rt) {
    if (people[lt] + people[rt] <= limit) {
      lt++; 
      rt--;
    } else {
      rt--;
    }
    answer++;
  }
  // 반복문을 while문으로 하고 
  // 배열이 push,pop 보다 연산이 덜 드는 방법으로 한것
  // 원리는 같다.
  // 구명보트에 타서 빠지는 과정을 나타낸 것이나 answer++ 항상 해줘야해서 조건문 밖으로 옮겼다.
  return answer;
}