Greedy Algorithm (1931 : 회의실 배정)

Greedy Algorithm (그리디 알고리즘)이란?

• Greedy 는 '탐욕스러운, 욕심이 많은' 이란 뜻입니다.
• 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다.
• 탐욕 알고리즘은 최적해를 구하는데 사용되는 근사적인 방법입니다.
• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장이 없습니다.
• 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들입니다.

 

탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택합니다.

2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사합니다.

3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.

 

탐욕 알고리즘을 적용하기 위해서는 문제가 다음 2가지 조건을 성립해야합니다.

• 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족됩니다.
• 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것입니다.

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결방법으로 구성됩니다.

• 이러한 조건이 성립하지 않은 경우에는 탐욕 알고리즘은 최적해를 구하지 못합니다.
• 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요합니다.
• 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있습니다.
• 이 구조를 매트로이드라고 합니다.
• 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여줍니다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아닙니다. 하지만 어느정도 최적에 근사값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.

 

탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 (매트로이드)가 있고,

이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있습니다. 따라서 실용적으로 사용 가능합니다.

 

 

근사 알고리즘 (Approximation Algorithm)이란?

• 근사 알고리즘 (approximation algorithm)은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미합니다.
• 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있습니다.

 

우리가 탐욕알고리즘을 적용하기 위해서 가져야할 조건 중 '탐욕 선택 속성', '최적 부분 구조' 2개가 있는데 최적 부분 구조 조건에서 우리는 Dynamic Programming을 떠올릴 수 있습니다. 

 

DP의 경우에는 문제가 Overlapping되기 때문에 다음에 풀 문제가 이전의 작은 문제의 결과에 영향을 받게 됩니다.

즉, 동일한 형식의 문제가 점점 커질 뿐, 이전의 경우에 영향을 받습니다.

 

하지만 그리디 알고리즘은 이와 달리 영향을 받아서는 안됩니다. 그래야 다른 경우의 결과와 상관 없이 최적해를 구할 수 있기 때문입니다.

 

 

그런데 위의 2가지 조건을 완전히 만족하는지, 그래서 해당 문제가 그리디 알고리즘을 사용할 수 있는 경우인지를 증명하기는 까다롭습니다.

일반적으로 그리디임을 증명하기 위해서는 수학적 증명이 동반되어야 합니다. 하지만 이 방식은 좀 어려우므로 우선 테스트 코드를 작성하여 정상 동작하는지 알아보는 방식으로 시도하는 경우가 많습니다.

(그리디가 아니라고 보는 경우는 반례를 1개만 찾아도 되기 때문에 상대적으로 쉽습니다.)

 

 

예시 - Action Selection 문제

그리디 알고리즘의 가장 대표적인 예시인 활동 선택(Action Selection) 문제에 대해서 알아보겠습니다.

활동 선택 문제는 N개의 활동이 있고 각 활동에는 시작 시간 및 종료 시간이 있을 때, 한 사람이 최대한 많이 할 수 있는 활동(Activity)의 수를 구하는 문제입니다.

즉, 각각의 활동(Activity)에는 시간이 소요되므로 하나를 선택했다면 그 동안 해당 시간에 다른 Activity를 할 수 없습니다.

이러한 상황일 때 가장 많은 활동에 참여하려면 어떻게 해야하는지 확인해보겠습니다.

 

위에서 각 활동과 그것의 시작 및 종료 시간이 설정되어 있는 것을 알 수 있습니다.

이 문제는 최대한 많은 활동을 해야하기 때문에 언제 시작하든 전체에서 가장 종료 시간이 빠른 것부터 선택해야합니다.

 

어차피 시작시간은 종료 시간 이전이므로 고려하지 않습니다

 

따라서, 종료 시간을 기준으로 정렬 후, 제일 먼저 끝나는 활동을 무조건 선택하고 끝났을 때 바로 다음에 선택할 수 있는 활동을 찾아 수행하는 방식

따라서 이 문제는 vector 컨테이너에 회의 스케줄을 저장하고 각각의 스케줄의 종료시점에 대해 정렬한 뒤,

1. 첫번째 time 변수는 종료시간이 가장 빠른 스케줄의 종료시점으로 초기화합니다.

2. 두번째 스케줄의 시작 시점이 첫번째 스케줄의 종료시점보다 크거나 같은지 확인합니다.

if(두번째 스케줄의 시작지점 >= 첫번째 스케줄의 끝 지점)
	=> time 변수를 두번째 스케줄의 종료 시점으로 저장
    =>count 수를 +1

else
	다음스케줄로 넘어간다

3. 모든 스케줄을 확인할 때 까지 2번을 반복합니다.

 

[코드]

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int value[10];

int main(){
	int N, end, begin;
    
    vector<pair<int,int>>schedule;
    
    cin >> N;
    for(int i=0;i<N; i++){
    	cin >> begin >> end;
        schedule.push_back(make_pair(end,begin));
    }
    
    sort(schedule.begin(), schedule.end());
    
    int time = schedule[0].first;
    int count = 1;
    for(int i=1; i<N; i++){
    	if(time <= schedule[i].second)
       	{
        	count++;
            time = schedule[i].first
        }
    }
    
    cout << count;
}