[알고리즘] 그리디 알고리즘(Greedy Algorithm)

간만에 블로그를 쓴다... 자주 쓰고자 다짐했지만..쩝

하지만! 지금부터라도 열심히 쓰면 되지 ㅎㅎ

오늘은 그리디 알고리즘(Greedy Algorithm)에 대해서 여러 블로그의 내용을 토대로 공부한 내용을 정리해보고자 한다.

 

👺그리디 알고리즘에 대해서

욕심쟁이 기법이니까 욕심 많을 것 같은 이모티콘으로 선정해보았다 ㅋㅋ

- 선택의 순간마다 당장 눈 앞에 보이는 최적의 기법으로 선택하여 최종적인 해답에 도달하는 알고리즘이다.

- 그 최종적인 답이 최적의 해라는 보장은 없다.

  => 순간마다 하는 선택은 지역적으로 최적이지만, 전역적으로 최적이라고 보장 못함

- 최적의 값의 근사값을 목표로 함

- 그리디 알고리즘이 적용될 수 있는 문제는 지역적, 전역적 모두 최적인 문제이어야 한다.

 

🤑 그리디 알고리즘 문제 풀이 방법

1. 현재 상태에서 최적의 선택

2. 선택된 해가 문제 조건 만족하는지 확인

3. 원래 문제가 해결 되었는지 확인, 안되었다면 위의 절차 다시 진행

 

🤝 그리디 알고리즘 속성

1. 탐욕 선택 속성(Greedy Choice Property)

 각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적 해를 구할 수 있는 경우

-> 각 단계에서 최적의 선택을 하면 전체에서도 최적의 결과를 가져온다!

2. 최적 부분 구조(Optimal Substructure)

전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우

-> 전체 문제를 작은 부분 문제로 나누어 각각 부분 문제에서 해를 구한 후 조합하여 전체의 최적 해 구하기

 

🟥 그리디 알고리즘 vs 동적 계획법

 

	그리디 알고리즘	동적 계획법
정의	각 단계에서 최적의 선택을 하는 방식으로 문제 해결	작은 문제의 해를 메모이제이션 하여 중복 계산(재귀) 하지 않고, 큰 문제 해결
성립 조건	1. 탐욕 선택 속성 2. 최적 부분 구조	1. 중복 부분 문제 2. 최적 부분 구조
중복 부분 문제	해결 X	해결 가능
상황	- 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구한다. - 최적이 아닌 경우가 될수 있거나 혹은 풀리지 않는 문제가 될수 있다.	- 모든 상황을 계산하여 최적의 경로를 구할 수 있다. - 시간 오래 걸림

 

 

💻 예시

1. 거스름돈

 - 1. 선택 절차 적용 : 거스름돈 문제에서 가장 큰 가치의 동전부터 선택

 - 2. 적절성 검사 : 선택된 동전의 가치 > 거스름돈 일 경우, 다음으로 작은 가치의 동전 선택

 - 3. 해답 검사 : 합 일치하면 해결

 

2. 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

//그리디 알고리즘
#include <iostream>
using namespace std;

int main()
{
    int n, k;
    int cnt = 0;
    cin >> n >> k;
    int A[n+1];
    for(int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    int i = n - 1;
    while(1)
    {
        if(A[i] > k)
        {
            i -= 1;
            continue;
        }
        else if(A[i] == k)
        {
            cnt++;
            break;
        }
        else
        {
            k = k - A[i];
            cnt++;
        }
    }
    cout << cnt;

    return 0;
}

 

 

3. 회의실 배정

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

// 그리디 알고리즘
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, start, end, time, cnt;
    cin >> n;
    vector<pair<int, int> > work;
    for(int i = 0; i < n; i++)
    {
        cin >> start >> end;
        work.push_back(make_pair(end, start));
    }
    sort(work.begin(), work.end());

    time = work[0].first; // 가장 빨리 끝나는 시간
    cnt = 1;
    for(int i = 1; i < n; i++)
    {
        if(work[i].second >= time)
        {
            time = work[i].first;
            cnt++;
        }
    }
    cout << cnt;

    return 0;
}