[탐욕법] 체육복, 구명보트

탐욕법(Greedy)

어떤 문제를 접했는데 당연히 DP로 해결하는 문제라고 생각했다.

다만 조건이 꽤 다양한 편이라서 성가신 문제라고 생각했는데, 효율성에서 완전 엉망이 됬다.

 

탐욕법은 DP와 같이 다양한 케이스중 최적해를 찾을 때 사용되는 알고리즘이다.

그리고 이는 DP보다 빠르다.

체육복

< 문제 >

굉장히 어려운 문제는 아니다만, DP로 오해하면 한 없이 복잡해진다.

최적의 경우, 최대한 많이, 그리고 많은 조건을 키워드로 탐욕법이라는 것을 유추해야 한다.

 

#include <string>
#include <vector>
 
using namespace std;
int student[35];
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    for(int i : reserve) student[i] += 1;
    for(int i : lost) student[i] += -1;
    for(int i = 1; i <= n; i++) {
        if(student[i] == -1) {
            if(student[i-1] == 1) 
                student[i-1] = student[i] = 0;
            else if(student[i+1] == 1) 
                student[i] = student[i+1] = 0;
        }
    }
    for(int i  = 1; i <=n; i++)
        if(student[i] != -1) answer++;
 
    return answer;
}

function solution(n, lost, reserve) {      
    return n - lost.filter(a => {
        const b = reserve.find(r => Math.abs(r-a) <= 1)
        if(!b) return true
        reserve = reserve.filter(r => r !== b)
    }).length
}

ES6

 

Javascript의 경우에는 배열을 실제로 제거해주었다.

순서는

1. filter로 옷을 잃어버린 사람들 중에서(a)

2. 빌려줄 수 있는 사람을 배열 b로 생성하고

3. 빌려 줄 수 있는 사람이 없다면 lost는 filter되지 않고(값을 남기고), 있다면 reserve에서 filter로 그사람을 찾아 제거한다. 

 

구명보트

< 문제 >

탐욕법에서는 중복과 마찬가지로 예제들이 정렬되어 있을 경우 쉽게 해결할 수 있는 경우가 있다.

최대 두명을 태울 수 있을 때, 가장 효율적으로 태우기 위해선

가장 작은 무게 + 가장 큰 무게 순으로 태워져야만 한다.

고로 오름차순으로 정렬 하고

가장 작은수부터 시작하는 인덱스와 가장 큰수부터 시작하는 인덱스로 나눈다음,

큰수는 하나씩 작은 쪽으로 이동해가며 가장 작은수와 limit을 통과할지를 결정한다.

limit에 통과할 경우 작은 수 역시 다음번 째 작은 수로 이동 후 계속 비교한다.

그렇게 작은수와 큰수가 교차 할때 종료하고

작은 수의 인덱스가 곧 동시탑승 가능했던 경우가 되므로 people.length에 빼주면 된다.

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