그리디 알고리즘 (Greedy Algorithm)

기본 아이디어

1. 현재 상태에서 **가장 좋은 선택(최적의 선택)** 선택
2. 이 선택이 이후 문제에 영향을 미칠지 고민하지 않고, 현재 문제만 고려
3. 이렇게 탐욕적인 선택을 반복하면 전체 문제를 해결할 수 있음

그리디 알고리즘의 특징

• 탐욕적 선택 속성 (Greedy Choice Property):
  • 현재의 탐욕적 선택이 나중에 영향을 미치지 않고, 전체 문제의 최적 해를 보장합니다.
• 부분 최적해 (Optimal Substructure):
  • 부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있어야 합니다.

중요: 그리디 알고리즘은 모든 문제에 적합하지는 않음

적용 가능한 문제의 조건

1. 탐욕적 선택 속성:
   • 각 단계에서의 최적의 선택이 전체 문제의 최적해를 보장해야 함
2. 최적 부분 구조:
   • 문제를 부분 문제로 나누었을 때, 각 부분 문제의 최적해를 합쳐도 전체 문제의 최적해가 되어야 함

 

그리디 알고리즘의 예제

1. 동전 거스름돈 문제

• 문제: 거스름돈을 주기 위해 동전의 최소 개수 구하기
• 조건: 동전의 종류는 1,5,10,50,100,5001, 5, 10, 50, 100, 5001,5,10,50,100,500원이며, 거스름돈은 항상 동전으로 나눌 수 있음

알고리즘:

1. 가장 큰 동전부터 사용하여 거스름돈을 줄이기
2. 남은 금액에 대해 다시 가장 큰 동전을 사용

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

int main() {
    int n; // 거스름돈
    cin >> n;

    vector<int> coins = {500, 100, 50, 10, 5, 1};
    int count = 0;

    for (int coin : coins) 
    {
        count += n / coin; // 현재 동전으로 줄 수 있는 최대 개수(큰 동전부터 시작)
        n %= coin;         // 나머지 금액 계산
    }

    cout << count << endl;
    return 0;
}

2. 회의실 배정 문제

• 문제: NNN개의 회의가 주어질 때, 회의실을 사용할 수 있는 최대 회의 개수 구하기
• 조건: 각 회의는 시작 시간과 종료 시간이 주어지며, 한 번에 한 회의만 진행

알고리즘:

1. 종료 시간이 빠른 회의를 우선적으로 선택
2. 선택한 회의와 겹치지 않는 회의를 반복해서 선택

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> meetings;

    for (int i = 0; i < n; i++) 
    {
        int start, end;
        cin >> start >> end;

        if (start >= end) 
        {
            cout << "종료시간이 시작시간보다 빠름" << endl;
            return 0; 
        }
        meetings.push_back({ end, start }); // 종료 시간 기준 (종료, 시작) 순으로 저장
    }
    sort(meetings.begin(), meetings.end()); // 종료 시간이 빠른 순으로 정렬

    int count = 0, last_end_time = 0;

    for (auto meeting : meetings) 
    {
        if (meeting.second >= last_end_time) 
        { // 시작 시간이 마지막 종료 시간 이후라면
            last_end_time = meeting.first;    // 종료 시간 업데이트
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

 

3. 배낭 문제 (Fractional Knapsack Problem)

• 문제: 물건의 무게와 가치가 주어질 때, 배낭에 담을 수 있는 최대 가치를 구하라.
• 조건: 물건을 쪼갤 수 있다.

알고리즘:

1. 무게당 가치가 높은 물건을 우선적으로 배낭에 담는다.
2. 남은 공간에 맞춰 물건을 쪼개서 넣는다.

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

struct Item 
{
    int weight;
    int value;
};

bool compare(Item a, Item b) 
{
    return (double)a.value / a.weight > (double)b.value / b.weight;
}

int main() {
    int n, W; // 아이템 수, 배낭 용량
    cin >> n >> W;

    vector<Item> items(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> items[i].weight >> items[i].value;//아이템struct 의 weight, value 저장
    }

    sort(items.begin(), items.end(), compare); // 무게 기준으로 정렬

    double max_value = 0;
    for (int i = 0; i < n; i++) 
    {
        if (W >= items[i].weight) 
        { // 물건 전체를 담을 수 있으면
            W -= items[i].weight;
            max_value += items[i].value;
        } 
        else 
        { // 물건을 쪼개서 넣음
            max_value += items[i].value * ((double)W / items[i].weight);
            break;
        }
    }

    cout << max_value << endl;
    return 0;
}