Back to Blog
알고리즘그리디동전회의실배정로프

0x11. 그리디 - 탐욕 알고리즘

그리디 알고리즘의 개념과 동전, 회의실 배정, 로프, 보물 문제 풀이를 정리한다.

0x11 그리디

0x00 알고리즘 설명

그리디 ( Greedy ) : 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘

그리디 알고리즘 푸는 과정

  1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안
  2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명
  3. 구현해서 문제를 통과

코딩테스트에서의 추천 전략

  • 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신
    • 짜서 제출해보고 틀리면 빠르게 손절
  • 100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다
    • 일단 넘어가고 다른 문제를 풀게 없거나 종료가 20-40분 남은 시점에 코딩 시작

0x01 연습문제 1 - BOJ 11047번 : 동전 0

DP로도 풀이 가능 D[i] = 가치의 합을 i로 만들 때 필요한 동전 개수의 최솟값 D[i] = min(D[i-A1], D[i-A2], ... D[i-AN]) + 1 O(NK), 시간초과

수학적 증명

  • 보조정리 1 동전을 최소로 소모하면서 물건값을 지불하려면 10/100원 동전은 4개 이하, 50/500원 동전은 1개 이하로 사용해야 한다.

  • 증명 10/100원 동전을 5개 이상 사용 -> 50/500원 동전으로 대체 50원 동전을 2개 이상 사용 -> 100원 동전으로 대체

  • 명제 동전을 최소로 소모하면서 물건값을 지불하려면 500원 동전을 최대한 많이 써야한다.

  • 증명 10, 50, 100원 동전으로는 물건값을 최대 10x4 + 50x1 + 100x4 = 490원만 감당 가능, 500원을 다 사용하지 않을 경우 10, 50, 100원 동전으로 물건값을 500원 이상 감당해야 함

코드는 너무 쉬워서 생략한다.

0x02 연습 문제 2 - BOJ 1931 : 회의실배정

Task scheduling problem

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

int n;
pair<int, int> meetings[100005];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++)
        cin >> meetings[i].second >> meetings[i].first;
    sort(meetings, meetings+n);

    int res = 0, cur = 0;
    for(int i=0; i<n; i++) {
        if(meetings[i].second < cur) continue;
        cur= meetings[i].first;
        res++;
    }
    cout << res << endl;
}

0x03 연습 문제 3 - BOJ 2217 : 로프

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

int w[100005];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> w[i];
    sort(w, w+n);

    int res = 0;
    for(int i=1; i<=n; i++)
        res= max(res, w[n-i] * i);
    cout << res << endl;
}

0x04 연습 문제 4 - BOJ 1026 : 보물

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] x B[0] + ... + A[N-1] x B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

int n;
int a[55], b[55];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<n; i++) cin >> b[i];
    sort(a, a+n);
    sort(b, b+n);

    int res = 0;
    for(int i=0; i<n; i++)
        res = a[i] + b[n-i-1];
    cout << res << endl;
}

문제 풀이

Note_ 1700번 멀티탭 스케줄링 : 멀티탭에 꽂혀 있는 전기용품 중 앞으로 가장 빨리 나오는 것을 찾아야 했다

else { // 멀티탭에 꽂혀 있는 전기용품 중 a에서 앞으로 가장 빨리 나올 위치를 이름과 함께 저장
    vector<pair<int, int>> idx;
    for(int s=1; s<=k; s++) {
        if(!power[s]) continue;
        bool vis= false;
        for(int e=i+1; e<=k; e++) {
            if(a[e]= s) {
                idx.push_back({e, s});
                vis= true;
                break;
            }
        }
        if(!vis) idx.push_back({k+1, s}); // a에서 나오지 않으면 k + 1로 처리
    }
    sort(idx.begin(), idx.end(), greater<pair<int, int>>());
    int target = idx[0].second; // 가장 늦게 사용할 전기용품을 뽑고 cur을 꽂으면 됨
    power[target] = false;
    power[cur] = true;
    ans++;
}

리뷰

알고리즘 수업에서 배웠던 기억이 있어서 익숙하게 복습했던것 같다.

미뤄뒀던 강의 뒷부분을 다시 들어보려고 한다.

다음은 빠르게 0X12 수학으로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편