그리디 알고리즘 정리

그리디 알고리즘 (탐욕법)

현재 상황에서 가장 좋은 것만 고르는 방법

기준에 따라 좋은 것을 선택함 -> 기준대로 정렬 알고리즘을 이용해 해결 가능

그리디 알고리즘으로 문제에 접근했을 때 정답을 얻을 수 있다고 보장되었을 경우 효과적임

-> 최소한의 아이디어가 정당한지 검토해야 정답 도출 가능함

반복되는 수열을 파악해야 함

 

풀 때 생각할 점

• 문제의 규칙(수열) 찾기
• 어떻게 정렬할지 생각하기
• 아이디어가 맞는지 검토하기

백준 문제

11047번

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>


using namespace std;

int coin[11];

int main() {
    int N, K;
    int i, t;
    int sum = 0;

    scanf("%d %d", &N, &K);
    for (i = 0; i < N; i++) {
        scanf("%d", &coin[i]); //오름차순으로 들어옴
    }
    
    for (i = N - 1; i >= 0; i--) {
        if (K == 0) break;

        sum += K / coin[i];
        K = K % coin[i];
    }

    printf("%d", sum);
    return 0;
}

동전의 가치가 오름차순으로 들어오기 때문에 반복문을 반대로 실행했다. 

필요한 동전의 최솟값이 필요하기 때문에 가장 큰 동전부터 K에서 나눈 몫을 sum에 더하고 K를 나머지로 만드는 과정을 반복해서 답을 도출했다.

 

1931번

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int main() {

    int N;
    int i;
    int a, b;
    int answer = 0;
    int firstTime=0;

    scanf("%d", &N);
    vector<pair<int, int>> v(N);
    for (i = 0; i < N; i++) {
        scanf("%d %d", &a, &b); 
        //끝난 시간을 기준으로 정렬할 거라서 끝난 시간을 pair에 먼저 넣음
        v[i].first = b;
        v[i].second = a;       
    }

    sort(v.begin(), v.end());

    for (i = 0; i < N; i++) {
        if (firstTime <= v[i].second) { //사용 가능
            firstTime = v[i].first;
            answer++;
        }
    }

    printf("%d", answer);
    return 0;
}

 

회의의 종료 시간을 기준으로 오름차순 정렬했다. 만약 종료 시간이 같을 경우 시작 시간을 기준으로 오름차순 정렬한다.

(이렇게 한다면 더 짧은 이용 시간인 회의를 우선으로 한다)

 

11399번

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n[1001];
int main() {
    int N;
    int i;
    int sum=0;
    int answer = 0;

    scanf("%d" , &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &n[i]);
    }

    sort(n, n + N);

    for (i = 1; i < N; i++) {
        n[i] = n[i - 1] + n[i];
    }
    for (i = 0; i < N; i++) {
        sum += n[i];
    }

    printf("%d", sum);
    return 0;
}

정렬한 후에 대기시간을 더한다.

 

1541번

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char x[51];  
    int n[50] = { 0 };
    int len, i,j=0;
    int sum = 0, num = 0;
    int answer;

    scanf("%s", x);
    len = strlen(x);
    for (i = 0; i < len; i++) {
        if (x[i] == '-'||x[i]=='+') {
            sum = sum + num;
            num = 0;
            if (x[i] == '-') {
                n[j] = sum;
                j++;
                sum = 0;
            }
        }
        else {
            num = num * 10 + (x[i] - '0');
        }
    }
    sum = sum + num;
    n[j] = sum;
    j++;

    answer = n[0];
    for (i = 1; i < j; i++) {
        answer = answer - n[i];
        //printf("n[%d]: %d\n", i, n[i]);                                                                                                   
    }
    printf("%d", answer);
    return 0;
}

'-'가 나오면 그 전의 수의 합을 배열에 저장하는 것을 반복한 후 배열의 처음에서 뒤의 것들을 다 뺀다.

 

13305번

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;

long long len[100001], price[100001];
int main() {
    int N;
    int i, j;
    long long minPrice = 0, nowPrice;
    
    scanf("%d", &N);
    for (i = 0; i < N-1; i++) {
        scanf("%lld", &len[i]);
    }
    for (i = 0; i < N; i++) {
        scanf("%lld", &price[i]);
    }

    minPrice = len[0] * price[0]; //처음에는 무조건 사야 함
    nowPrice = price[0];

    for (i = 1; i < N - 1; i++) {
        if (nowPrice > price[i]) { //원래 가격이 더 싸면 원래 가격으로 더 삼, 아니면 가격 바꾸기
            nowPrice = price[i];
        }
        minPrice += (nowPrice * len[i]);
    }

    printf("%lld", minPrice);
    return 0;
}

현재 기름 가격과 다음 기름 가격을 비교해서 원래 가격이 더 싸다면 원래 가격으로, 아니라면 가격을 바꿔서 더한다.

이를 반복했을 때 나온 결과가 최저 가격이 된다.