Greedy Algorithm

강한친구·2022년 4월 21일

알고리즘 문제풀이 기법

목록 보기

22/27

회의실 배정 문제

그리디 알고리즘의 대표주자문제이다.
문제

시작순으로 정렬하기

반례를 찾아보면 쉽게 안된다는걸 알 수 있다.

이런 예제가 있다면 실제로 가능한 값은 (2, 3) (4, 5) 이겠지만, 우리가 받아볼 결과는 1, 10하나이다.

따라서 이렇게는 안된다.

끝나는 순으로 정렬

이런 예제가 오더라도

2 3
4 5
1 10

이렇게 정렬하면 문제를 풀 수 있다.

현재 회의가 끝나는 시간을 curr로 잡고, for문으로 전체 회의를 조회하면서, 다음회의의 시작시간이 현재회의의 끝나는 시간보다 늦다면 (크다면) cnt++ 한 후, 다음 회의 끝나는 시간을 curr로 잡는것이다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;

struct Point {
    int start;
    int end;
};

vector<Point> vec;

bool comp (Point a, Point b) {
    if (a.end == b.end) return a.start < b.start;
    else return a.end < b.end;
} 

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        Point p;
        cin >> p.start >> p.end;
        vec.push_back(p);
    }
    sort (vec.begin(), vec.end(), comp);

    // for (int i = 0; i < n; i++) {
    //     cout << vec[i].start << " " << vec[i].end << "\n";
    // }

    int curr = vec[0].end;
    int ans = 1;

    for (int i = 1; i < n; i++) {
        if (curr <= vec[i].start) {
            ans++;
            curr = vec[i].end;
        }
    }
    cout << ans;
}

쉬운문제인데 좀 많이 틀렸다.
bool comp 과정에서 a.end == b.end로 비교해야하는데, a.start == b. start로 비교해버렸다...

괄호 넣기

문제

가장 작은 수를 찾으려면?

작은수 - 큰수
이 구조가 나오면 음수가 나오는것을 알 수 있다.

따라서 첫번째 마이너스 뒤를 먼저 다 계산하여 가장 큰 수를 만들어놓고, 맨 앞에 수에서 이를 빼는것이 정답인것이다.

세부적인 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

bool flag = false;
string str;

int temp = 0;
int sum = 0;

int main( ){
    cin >> str;

    for (int i = 0; i <= str.size(); i++) {
        if (str[i] == '+'|| str[i] == '-' || i == str.size()) {
            if (!flag) {
                sum += temp;
                temp = 0;
            } else if (flag) {
                sum -= temp;
                temp = 0;
            }
            if (str[i] == '-') flag = true;
        } else {
            temp *= 10;
            temp += str[i] - '0';        }
    }
    cout << sum;
}

정리

이 아이디어는 가지고 있었는데, 이를 구현하는 과정에서 조금 어려움을 겪었다.

수가 무조건 한자리수만 있는것은 아니다보니, 문자화 된 수를 처리해주려면

temp *= 10;
temp += str[i] - '0';

위와 같은 처리가 필요했다.

파이썬이나 자바와는 다르게 cpp에서는 char숫자를 int로 바꾸려면

char a = i;
int n = a - '0';

이라는 특수한 공식을 사용해야하기에 이를 기억해두면 좋을것같다.

주유소문제

또 자주 나오는 문제이다. 이를 응용하여 번갈아가면서 들리거나 교차하는 문제도 종종 나온다.

문제

풀이 아이디어

현재 주유소의 가격이 다음 주유소보다 싸다면, 다음에 이동할 거리분까지 지금 다 넣고 이동하자는 전략이다.

최초 풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, val;
int ans = 0;
int distance_sum = 0;
vector <int> distancer;
vector <int> price;

int main() {
    cin >> n;

    for (int i = 0; i < n-1; i++) {
        cin >> val;
        distance_sum += val;
        distancer.push_back(val);
    }
    for (int i = 0; i < n; i++) {
        cin >> val;
        price.push_back(val);
    }
    price.back() = 1000000001;
    int min_num = 1000000001;
    
    for (int i = 0; i < n; i++) {
        min_num = min(price[i], min_num);
    }
    int dis_counter = 0;
    for (int i = 0; i < n; i++) {
        if (price[i] == min_num) {
            int temp = price[i] * distance_sum;
            ans += temp;
            break;
        } else {
            int temp = price[i] * distancer[dis_counter];
            ans += temp;
            distance_sum -= distancer[dis_counter];
        }
        dis_counter++;
    }
    cout << ans;
}

값이 가장 적은 주유소에서 나머지 기름을 다 넣고, 그 전까지는 자기 다음칸까지 갈 만큼만 주유하는 방식이다.

이 방식의 문제점은, 항상 최적의 방식을 보장하지 못한다는점이다.

두번째 풀이

#include <iostream>
#include <algorithm>
using namespace std;

long long dist[100000];
long long price[100000];

long long n, curr, ans = 0;

int main() {
    cin >> n;

    for (int i = 1; i < n; i++) {
        cin >> dist[i];
        
    }
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }

    curr = price[0];
    ans = price[0] * dist[1];

    for (int i = 1; i < n; i++) {
        if (curr < price[i]) {
            ans += curr * dist[i+1];
        } else {
            curr = price[i];
            ans += curr * dist[i+1];
        }
    }
    cout << ans;
}