Algorithm 개념정리: Greedy Algorithm

Greedy Algorithm이란?

Greedy Algorithm은 최적의 값을 구해야 하는 상황에서 사용되는 기법이다.

'매 선택에서 당장의 결과가 가장 최적인 답을 선택'하여 나아가는 과정이기 때문에,

근시안적으로 최적의 경로를 찾아가다보면 결과적으로도 최적의 결과에 도달할 수 있을 것이라는 사고방식으로 문제를 풀어나는 방법이다.

 

그렇기 때문에 풀려고 하는 문제가 Greedy Algorith에 적합한 문제인지 판별 후 사용해야 한다.

당장의 매 선택에 대해서는 최적이지만 종합적으로 봤을 때 문제의 결과가 최적의 값으로 도출된다는 보장은 없기 때문이다.

 

Greedy Algorithm으로 접근할 수 있는 대표적인 상황이 '가장 적은 화폐 개수로 돈 계산하기'이다.

50000, 10000, 5000, 1000, 500 100, 50, 10원권이 있다고 할 때,

 

전체 금액에서 가장 큰 화폐단위부터 차례대로 나누어 화폐 개수를 카운트 해주면 된다.

현재 화폐단위보다 적은 금액일 경우, 연산의 나머지값을 그 다음 화폐 단위로 금액의 나누기 연산을 계속적으로 진행하면

최소한의 화폐 개수로 구성할 수 있는 결과 값이 도출된다.

 

ex) 76,550원을 최소 화폐 개수로 지불하는 경우의 화폐 개수 카운트

76,550 / 50,000 = 1 (나머지 = 26,550) -> count++;

26,550 / 10,000 = 2 (나머지 = 6,550) -> count+=2;

6,550 / 5,000 = 1 (나머지 = 1,550) -> count++;

1,550 / 1,000 = 1 (나머지 = 550) -> count++;

550 / 500 = 1 (나머지 = 50) -> count++;

50 / 50 = 1 (나머지 = 0) -> count++;

총 7개의 화폐로 76,550원을 지불할 수 있다는 결과가 나온다.

 

 

Greedy Algorithm 적용하기

Greedy Algorithm을 적용해 볼 수 있는 간단한 문제를 한번 풀어보자.

 

🤠 모험가 길드 (난이도: ⭐)

* 제한시간 1초, 메모리 제한 128MB
모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정한다.
모험가 그룹을 안전하게 구성하기 위해 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정한다.
주어진 인력 내에서 최대 몇개의 여행 그룹을 구성할 수 있을지 그 개수를 출력해보자.
이때 모험가의 수 N의 범위는 다음과 같다. (1 <= N <= 100,000)

입력 예시) 
5
2 3 1 2 2 

출력 예시)
2

 

위 문제는 Greedy Algorithm을 적용해 풀이할 수 있다.

 

🌿 풀이과정

1) 입력받은 모험가의 공포도를 오름차순 정렬한다.

2) 현재 구성하는 그룹의 구성원 개수를 카운트한다.

3) 그룹 구성원 수가 현재 공포도보다 크거나 같다면 그룹을 구성하고, 구성원 개수 카운트를 0으로 초기화한다.

4) 2)~3)번 과정을 전체 구성원의 개수만큼 반복하여 최종적으로 구성된 그룹의 수를 카운트한다.

 

풀이과정을 도식화하면 아래와 같다.

공포도 순으로 멤버를 오름차순 정렬한 뒤, 멤버를 차례로 순회하며 당장 만들 수 있는 그룹의 개수를 차례로 카운트한다.

직관적으로 적은 멤버수로 만들 수 있는 그룹부터 구성해야지 가장 많은 개수의 그룹을 구성할 수 있으므로 Greedy Algorithm 기법으로 문제를 해결할 수 있는 것이다.

 

 

 

해당 로직을 소스코드로 구현하면 아래와 같이 구현할 수 있다.

 

💻 소스코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
    
    int n, count=0, result= 0;
    cin >> n;
    
    vector<int> explorer(n);
    for (int i=0; i<n; i++){
        cin>>explorer[i];
    }
    
    // 오름차순 정렬
    sort(explorer.begin(), explorer.end());
    
    
    for (int e:explorer){
        count++;
        if(count>e){
            result++;
            count=0; // 사람 수 초기화
        }
    }
    cout<<"count: "<<count<<endl;
    
    return 0;
}