[230327] 구명보트: Greedy 알고리즘

 

 

 

탐욕 알고리즘(Greedy Algorithm)

• greedy: 탐욕스러운, 욕심이 많은
• 즉, 매 순간 가장 좋아 보이는 것만 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
• 기준에 따라 좋은 것을 선택하는 알고리즘이므로, 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준이 제시된 경우에 응용한다.

예제: 거스름돈

🧸 문제
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

문제 해설

동전의 최소 개수를 구해야 하는 문제이므로, 가장 큰 화폐 단위부터 돈을 거슬러 줘야 한다.

거스름 돈이 N원일 때, 500원으로 최대한 많이 거슬러주고, 100원, 50원, 10원을 순서대로 써서 거슬러주면 된다.

 

만약 N = 1260원이라면?

 

[step 1] 남은 돈: 1260원

점원에게 1260원이 있고, 이제 손님에게 동전을 거슬러줘야 한다.

[step 2] 500원 - 남은 돈: 260원

500원으로 거슬러 줄 수 있는 돈은 1000원이다. 그래서 260원이 남는다.

[step 3] 100원 - 남은 돈: 60원

260원에서 100원으로 거슬러 줄 수 있는 돈은 200원이다. 그래서 60원이 남는다.

[step 4] 50원 - 남은 돈: 10원

60원에서 50원으로 거슬러 줄 수 있는 돈은 50원이다. 그래서 10원이 남는다.

[step 5] 10원 - 남은 돈: 0원

10원 1개를 써서 거스름 돈을 모두 거슬러줬다.

 

그래서 결론적으로, 500원 2개, 100원 2개, 50원 1개, 60원 1개 ⇒ 동전이 총 6개가 필요하다.

 

코드로 구현해보자.

 

코드 구현

let n = 1260;
let count = 0;

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

for(let i = 0; i < coinType.length; i++) {
	count += (n / coinType[i]); // 해당 화폐로 거슬러 줄 수 있는 동전 개수 세기
	n %= coinType[i];
}

코드를 실행하면 화폐의 종류만큼 반복 수행한다. 그래서 화폐 종류가 K개라고 하면 코드의 **시간 복잡도는 O(K)**이다. 시간 복잡도는 거스러 줘야할 돈 N과는 상관없다!

이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러줘야하는 금액의 크기와는 무관하다.

 

그리디 알고리즘의 정당성

그리디 알고리즘으로 문제를 풀게 되면 최적의 해를 찾을 수 없는 가능성이 더 크다.

그러나 거스름돈 문제에서처럼 ‘가장 큰 화폐 단위부터’ 돈을 거슬러주듯이, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 경우엔 효과적이고 직관적이다.

그리디 알고리즘으로 해법을 찾았을 때 그 해법이 정당한지 검토도 해보아야만 한다.

거스름 돈 문제가 그리디 알고리즘에 적합한 이유는?

→ 가지고 있는 동전 종류 중에서 큰 단위가 작은 단위의 배수 형태이기 때문!

예로 들어서 800원을 거슬러줘야 하는데 동전의 단위가 [500, 400, 100]인 경우가 있다면?

• 그리디 알고리즘은? (500 + 100 + 100 + 100) 총 4개 동전이 필요함
• 최적의 해는? (400 + 400) 총 2개의 동전이 필요함

즉, 거스름 돈 문제의 해결 아이디어는 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만 수행하면 된다 였고,

최적의 해를 구했기에 이 해당에서 그리디 알고리즘은 정당했다.

 

정리

• 그리디 알고리즘은 정당성 분석이 중요하다.
  • 순서 기준이 있는가? (큰/작은 순서대로)
  • 큰 단위가 작은 단위의 배수 형태인가?
• 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하자.

 

 

구명보트

문제

 

첫 풀이

1. people을 내림차순으로 정렬한다.
2. 그렇게 정렬한 people을 뒤에서부터 가장 작은 수를 보고, 앞에서부터 큰 수를 하나씩 보면서 두 수가 무게 제한을 넘는지 여부를 본다.
   1. 무게 제한 넘지 않으면? 앞에서 본 큰 수도 People에서 없앤다.

function solution(people, limit) {
    let answer = 0;
    people.sort((a, b) => b - a);
    
    while(people.length !== 0) { 
        const limitNum = limit - people[people.length - 1];
        answer++;
        people.pop();
        
        for(let i = 0; i < people.length; i++) {
            if(people[i] / limitNum <= 1) { 
                people.splice(i, 1); 
                break;
            }
        } 
    }
    return answer;
}

 

결과

정확성 테스트는 모두 통과하는데, 효율성이 좋지 않아서 효율성 테스트는 모두 실패한다.

for문에서 첫 번째 인덱스 값이 limitNum보다 크면 후에 값들도 limitNum보다 클 것이므로 뒤에 값들을 더 볼 필요도 없다. 그래서 break;로 for문을 나오는 조건을 추가하였다.

for(let i = 0; i < people.length; i++) {
      **if(i === 0 && people[0] > limitNum) break;**
      if(people[i] <= limitNum) { 
          people.splice(i, 1); 
          break;
      }
  }

이렇게 하니 효율성 테스트도 통과한다.

 

전체 코드

function solution(people, limit) {
    let answer = 0;
    people.sort((a, b) => a - b);
    
    while(people.length !== 0) { 
        const limitNum = limit - people[people.length - 1];
        answer++;
        people.pop();
        
        for(let i = 0; i < people.length; i++) {
            if(i === 0 && people[0] > limitNum) break;
            if(people[i] <= limitNum) { 
                people.splice(i, 1); 
                break;
            }
        } 
    }
    return answer;
}

 

 

다른 풀이

짝 지어지는 개수(i)를 구하는게 주목적으로 두고 푸는 풀이다.

i가 뒤의 큰 값과 짝이 지어지면 +1이 되므로, 결과적으로 i 값은 짝지어진 수를 의미하게 된다.

그래서 people.length - i 는 구명보트 개수의 최솟값이 된다!

function solution(people, limit) {
    people.sort((a, b) =>  a - b);
    for(var i = 0, j = people.length - 1; i < j; j--) {
        if(people[i] + people[j] <= limit) i++;
    }    
    return people.length - i;
}