알고리즘 - 그리디

1931 - 회의실 배정

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

int st[1000000];
int ed[1000000];

// 종료 시간 기준 정렬 but 같으면 시작 시간 기준 정렬
bool compare(int i, int j) {
    if (ed[i] == ed[j]) {
        return st[i] < st[j];
    }
    return ed[i] < ed[j];
}

int main() {
    int n;
    cin >> n;

    int list[1000000];
    for (int i = 0; i < n; i++) {
        cin >> st[i] >> ed[i];
        list[i] = i;
    }

    // 회의 리스트를 종료 시간 기준으로 정렬
    sort(list, list + n, compare);

    int count = 0;
    int last = 0;

    // **겹치지 않는 작업** 최대 개수 선택
    for (int i = 0; i < n; i++) {
        int idx = list[i];
        if (st[idx] >= last) {
            count++;
            last = ed[idx];
        }
    }

    cout << count;
    return 0;
}

이 문제는 회의실이 겹치지 않게 최대로 회의를 하는 경우에 최대 몇번 할 수있는지를 구하는 문제이다.

bool compare(int i, int j) {
    if (ed[i] == ed[j]) {
        return st[i] < st[j];
    }
    return ed[i] < ed[j];
}

이 함수는 sort(list, list + n, compare); 에 사용되는 정렬 기준이다.

sort(list, list + n, compare);

정렬을 해주는 함수이다.

for (int i = 0; i < n; i++) {
        int idx = list[i];
        if (st[idx] >= last) {
            count++;
            last = ed[idx];
        }
    }

겹치지 않는 작업을 count로 올려주며 확인을 해준다.

cout << count;

아까 확인해준 count를 출력해주면 회의실이 겹치지 않게 최대로 회의를 하는 경우에 최대 몇번 할 수있는지를 구할 수 있다.

 

1541 - 잃어버린 괄호

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

int main() {
    string s;
    cin >> s;
    int answer = 0, temp = 0, length = (int)s.length(), minus = false;
    
    for (int i = 0; i < length; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            temp = temp * 10 + (s[i] - '0');
        } else if (s[i] == '+') {
            if (minus) {
                answer = answer - temp;
            } else {
                answer = answer + temp;
            }
            temp = 0;
        } else if (s[i] == '-') {
            if (minus) {
                answer = answer - temp;
            } else {
                answer = answer + temp;
            }
            temp = 0;
            minus = true;
        }
    }

    if (minus) {
        answer = answer - temp;
    } else {
        answer = answer + temp;
    }

    cout << answer;
    return 0;
}

이 코드는 괄호를 가지고 식을 만든후 이 식에서 괄호를 제외 한 식을 주어졌을때(예시 : 55- 50 + 40 = -35 ) 어디에 괄호를 쳐야 정답이 될지를 출력하는 문제이다

for (int i = 0; i < length; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            temp = temp * 10 + (s[i] - '0');
        } else if (s[i] == '+') {
            if (minus) {
                answer = answer - temp;
            } else {
                answer = answer + temp;
            }
            temp = 0;
        } else if (s[i] == '-') {
            if (minus) {
                answer = answer - temp;
            } else {
                answer = answer + temp;
            }
            temp = 0;
            minus = true;
        }
    }

입력을 S에 받은후에 확인을 해주고

if (minus) {
        answer = answer - temp;
    } else {
        answer = answer + temp;
    }

이후 false면 아니면으로 또 해준다