그리디 알고리즘(Greedy Algorithm)의 개념, 예제 코드

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

매 단계에서 '가장 좋아보이는' 해답을 선택하는 알고리즘이다. 

 

지역적인 최적의 해결 방법을 통해 전역적인 최적의 해결 방법을 찾는 것이다. 

아래는 그리디 알고리즘으로 해결할 수 있는 대표적인 두 문제이다.

 

1) 최단 작업 우선 스케일링

 

예제를 통해 알아보자.

 

1. 은행 창구에 줄을 서서 사람들이 차례를 기다리고 있다. 각자의 업무를 보는 데 걸리는 시간은 각자 다르다.
2. 대기열에 기다리고 있는 사람들은 평균 대기 시간이 최소화 되도록 순서를 재배치하는 것에 동의했다.
3. 평균 대기 시간이 최소가 되는 순서 배치를 구하시오.

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

template<typename T>
auto compute_waiting_times(vector<T> &service_time) {
	vector<T> W(service_time.size());
	W[0] = 0;

	for (auto i = 1; i < service_time.size(); i++) {
		W[i] = W[i - 1] + service_time[i - 1];
	} // 각 대기자의 총 대기 시간을 나타내는 배열
	return W; 
}

template<typename T>
void print_vector(vector<T>& V) {
	for (auto& i : V) {
		cout.width(2);
		cout << i << " ";
	}
	cout << endl;
}

template <typename T>
void compute_and_print_waiting_times(vector<T>& service_times) {
	auto waiting_times = compute_waiting_times<int>(service_times); // 각 대기자의 대기 시간을 담은 벡터

	cout << " - 처리 시간 : ";
	print_vector<T>(service_times);

	cout << " - 대기 시간 : ";
	print_vector<T>(waiting_times);

	// 평균 대기 시간 구하기
	auto ave_waiting_times = accumulate(waiting_times.begin(), waiting_times.end(), 0, 0) / waiting_times.size();
	// accumulate(first, last, sum, myfun); 
	// myfun is a function for performing any specific task.
	cout << " - 평균 대기 시간" << ave_waiting_times;
	cout << endl;
}

int main() {
	vector<int> service_times{ 8,1,2,4,9,2,3,5 };

	cout << "[처음 일 처리 시간 & 대기 시간]" << endl;
	compute_and_print_waiting_times<int>(service_times);

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

	cout << endl;
	cout << "[정렬 후 일 처리 시간 & 대기 시간]" << endl;
	compute_and_print_waiting_times<int>(service_times);
		
	return 0;
}

해결 방법은 간단하다.

배열을 오름차순으로 정렬하면 평균 대기시간이 최소가 되는 배열로 바뀐다. 

 

2) 배낭 문제

 

1. 여러가지 물건들이 주어졌을 때 , 각 물건들의 무게와 가격은 다르다. 
2. 물건들이 가격 합이 최대가 되도록, 최대 무게를 T까지 실을 수 있는 배낭에 담으려 한다. 
3. 전체 물건의 가격이 최대가 되는 경우를 구하시오. 

이러한 배낭 문제는 NP-완전 문제라고 알려져 있다. 

문제를 조금 변경해서, 물건의 일부분을 덜어서 배낭에 담을 수 있다고 가정하자. 

이것을 분할 가능 배낭 문제라고 하는데, 

 

비슷하게 가격별로 내림차순의 형태로 배열을 정렬한 다음에, 

for문에서 순회를 돌며 배낭의 용량이 가득찰 때까지 현재 물체의 개수를 증가시킨다.

 

초과된 경우, 초과된 만큼의 무게를 따로 변수에 담아 '제거할 마지막 물체의 무게'를 구한다. 

그리고 배낭에 마지막으로 담은 물체를 꺼내와 해당 변수만큼 빼주면 된다. 

값어치도 역시 조절해주면 되는데, "무게 당 값어치 * 제거될 무게"의 값을 value에서 빼준다. 

 

그리고 반환된 벡터의 내용을 출력해주면 끝!

 

전체 코드

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

struct Object {
	int id;
	int weight;
	double value;
	double value_per_unit_weight;

	Object(int i, int w, double v)
		:id(i), weight(w), value(v), value_per_unit_weight(v/w) 
	{	}

	// std::sort()에서 사용
	inline bool operator< (const Object& obj) const {
		return this->value_per_unit_weight < obj.value_per_unit_weight;
	} // 단위 무게당 값어치를 계산하여 비교

	friend ostream& operator << (ostream& os, const Object& obj);
};

ostream& operator<<(ostream& os, const Object& obj) {
	os << "[" << obj.id << "] 가격 : " << obj.value
		<< "\t무게 :" << obj.weight
		<< "kg\t단위 무게 당 가격 : " << obj.value_per_unit_weight;
	return os;
}

// 분할 가능 배낭 문제 알고리즘 구현 함수 
auto fill_knapsack(vector<Object>& objects, int knapsack_capacity) {
	vector<Object> knapsack_contents;
	knapsack_contents.reserve(objects.size());

	// 가치 있는 순대로 정렬 (내림차순) 
	sort(objects.begin(), objects.end());
	reverse(objects.begin(), objects.end());

	// 가장 가치 있는 물건들 먼저 배낭에 추가 
	auto current_object = objects.begin();
	int current_total_weight = 0;
	while (current_total_weight < knapsack_capacity && current_object != objects.end()) {
		knapsack_contents.push_back(*current_object);

		current_total_weight += current_object->weight;
		current_object++;
	}

	// 마지막 추가한 물건에 의해 배낭 최대 허용 무게가 초과된 경우
	int weight_of_last_obj_to_remove = current_total_weight - knapsack_capacity; // 조금이라도 더 담겠다.
	Object& last_object = knapsack_contents.back();
	if (weight_of_last_obj_to_remove > 0) {
		last_object.weight -= weight_of_last_obj_to_remove;
		last_object.value -= last_object.value_per_unit_weight * weight_of_last_obj_to_remove;
	}
	return knapsack_contents; 
}

int main() {
	vector<Object> objects; 
	objects.reserve(7); // vector의 capacity를 설정하는 메소드

	vector<int> weights{ 1,2,5,9,2,3,4 };
	vector<double> values{ 10,7,15,10,12,11,5 };
	for (auto i = 0; i < 7; i++)
		objects.push_back(Object(i + 1, weights[i], values[i]));

	int knapsack_capacity = 7;
	auto solution = fill_knapsack(objects, knapsack_capacity);

	cout << "[배낭에 넣을 물건들 (최대 용량 = " << knapsack_capacity << ")]" << endl;
	for (auto& o : solution) {
		cout << o << endl;
	}
	cout << endl;
}

 

---

 

모든 문제에 그리디를 적용할 수 있을까?

 

아닙니다. 

특정 속성을 가지고 있는 문제만이 그리디 접근 방식을 사용할 수 있다.

 

1. 최적 부분 구조(optimal substructure) 

주어진 문제(P)에 대해 최적의 솔루션이, P의 부분 문제들의 최적의 솔루션으로 구성된 경우

문제 P가 최적의 부분 구조를 갖는다. 

 

2. 그리디 선택(greedy choice)

문제 P에 대한 지역적 최적 솔루션을 반복적으로 선택해 전체 최적 솔루션을 구할 수 있을 때

그리디 선택 속성을 갖는다고 말한다.