[JS] 코딩 테스트 문제가 너무 어려워? 욕심이 너무 없어서 그래! 탐욕법 Greedy

[JS] 코딩 테스트 문제가 너무 어려워? 욕심이 너무 없어서 그래! 탐욕법 Greedy

 

Greedy Algorithm

탐욕법은 각 단계에서 현재 상태에서 최선이라고 생각되는 선택을 이어나가 최종적인 해결책을 찾는 방법이다.

전체적인 최적의 해를 보장하지는 않기 때문에 탐욕법을 적용할 수 있는 문제가 한정된다. 탐욕법을 적용할 수 있는 문제인지 아닌지에 대한 눈을 갖기 위해서는 문제를 많이 풀어보는 것이 가장 효과적이다.

 

예시 문제를 보면서 탐욕법에 대해 알아가보자.

 

문제상황

어떠한 물건을 사고 고객이 값을 지불했다. 거스름돈을 거슬러줘야 하는데 동전으로 거슬러주려 한다. 동전의 단위는 500, 100, 50, 10원이다. n원을 거슬러줄 때 가장 적은 동전의 개수는 어떻게 되는가?

 

문제풀이

동전의 리스트를 내림차순으로 배열하고, 최대 단위의 동전과 거스름돈을 비교하며 동전의 단위를 내려나간다.

function solution(n) {
  const coin = [500,100,50,10];
  let answer = 0;
  let coinIdx = 0;
  
  while(n > 0 && coinIdx >= coin.length) {
    if(n >= coin[coinIdx]){
      n -= coin[coinIdx];
      answer++;
    } else coinIdx++;
  }
  
  return n === 0 ? answer : -1;
}

 

동전을 가능한 큰 단위로 내려가며 거슬러주기 때문에, 현재 상황에서 가능한 가장 최선의 선택을 하는 것이다. 이를 반복하여 최선의 거스름돈의 개수를 돌려주고, 돌려줄 수 없다면 -1을 반환한다.

 

이렇게 탐욕법은 locally optimized 한 선택을 이어나간다. 미래에 내 선택이 어떤 결과를 일으킬지 따위는 고려하지 않는다.

내가 보유 중인 코인이 미래에 폭등할 거란 확신이 있어도 당장 이득을 보고 있다면 팔아버린다. 이와 같이 현 상황에서 좋은 결과는 얻을 수 있지만 항상 최선을 보장하지는 않기 때문에 특정 문제에만 적용할 수 있는 것이다.

 

이러한 탐욕법을 적용할 수 있는 문제는 현재의 선택이 미래의 선택에 영향을 주지 않는다는 특성을 띤다. 이를 greedy choice property라고 한다. 또한 탐욕법을 적용할 수 있는 문제는 하나의 큰 문제를 여러 개의 작은 문제로 나눠, 작은 문제의 대한 최적의 해가 전체 최적의 해가 된다는 특성을 띈다. 이를 optimal substructure라고 한다.

optimal substructure && greedy chice property의 상태에서만 탐욕법이 최적의 해를 도출할 수 있다. 따라서 문제의 조건을 탐욕법을 풀 수 있는 상태로 정렬해주어야 한다. 위 동전 문제에서는 그 정렬이 동전의 단위를 내림차순으로 정렬하는 것이었다.

 

탐욕법은 속도가 굉장히 빠르다. DP보다도 말이다.

 

자. 이제 문제를 하나 더 풀어보자.

 

(아래 내용에서는 이 문제에 대한 스포일러가 등장한다. 한 번 풀어본 이후에 아래 내용을 정독하자.)

프로그래머스

 

고속도로를 이동하는 차량들이 모두 한 번씩은 거칠 수 있는 단속카메라의 최소 설치 개수를 구해야 하는 문제이다.

 

1.  탐욕법의 조건을 위해서는 먼저 차량의 순서를 재정렬 해야 한다. 카메라를 놓기 위한 최적 조건을 구하기 위해서 차량의 진입 지점을 기준으로 하여 내림차순으로 차량을 정렬한다.

routes.sort((a, b) => b[0] - a[0]);

 

2. 리스트의 첫 번째 차량이 진입하는 시점에 카메라를 설치한다.

const cameras = [routes.shift()];

 

3. 리스트를 순회하며, 차량과 카메라의 시점을 비교해 새로운 카메라를 설치한다. 차량의 경로가 카메라와 겹치지 않는다면 새로운 카메라를 설치하는 것이다.

while (routes.length > 0) {
    const [on, out] = routes.shift();
    const [lastOn, lastOut] = cameras.at(-1); 
        
    if (on > lastOut || out < lastOn) cameras.push([on, out]); 
}

 

아래는 전체 코드이다.

function solution(routes) {
    routes.sort((a, b) => b[0] - a[0]); 
    const cameras = [routes.shift()]; 
    
    while (routes.length > 0) {
        const [on, out] = routes.shift();
        const [lastOn, lastOut] = cameras.at(-1); 
        
        if (on > lastOut || out < lastOn) cameras.push([on, out]); 
    }
    
    return cameras.length;
}

 

마치며

학교에서 수업시간에 선생님께서 탐욕법에 대해 가르쳐주신 적이 있었다. 당시에는 대충 들었었는데 지금 복기해 보니 정말 훌륭하신 선생님이었다. 알고리즘 문제를 풀 때에는 항상 그 선생님 생각이 난다..