[알고리즘] 그리디 알고리즘 - 개요 및 최단 작업 우선 스케줄링

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

그리디 알고리즘

개요

　그리디(greedy) 알고리즘은 매 시점에서 가장 이상적인 선택을 지향하는 알고리즘이다. 이 방법론은 지역(local)적으로 최적화된 해답들을 도출하면서, 그 해답들로부터 전역(global)적인 최적해를 구축하는 전략을 채택한다. 그리디 알고리즘은 각 선택의 순간마다 최적의 결정을 내리지만, 이 일련의 결정들이 꼭 최적의 결과를 보장하는 것은 아니다. 그러나 특정 문제에 대해서는 이 알고리즘이 실제로 최적의 결과를 보장하기도 하고, 복잡하고 시간 소모적인 문제를 효과적으로 근사해결하는 데에 종종 활용되기 때문에 그 가치는 높다고 할 수 있다.

 

　이러한 그리디 알고리즘의 단순하고 직관적인 접근법은 그것의 한계를 동시에 내포하고 있다. 즉, 그리디 특성을 지닌 문제에 대해서만 그리디 알고리즘이 적용 가능하다. 여기서 그리디 속성이란 최적 부분 구조와 그리디 선택이라는 두 가지 속성을 의미한다. 이 개념들은 여기서는 간략하게만 다루고, 추후에 더 자세히 설명하도록 하겠다.

 

• 최적 부분 구조(optimal substructure): 주어진 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성될 경우
• 그리디 선택(greedy choice): 주어진 문제 P에 대한 지역적 최적 솔루션을 반복적으로 선택하여 최적 솔루션을 구할 수 있는 경우

 

---

최단 작업 우선 스케줄링

개요

　그리디 방식으로 해결할 수 있는 대표적인 문제 중 하나인 최단 작업 우선 스케줄링(shortest-job-first schedule - SJF)에 대해 알아보자. 이는 대기열에 머물고 있는 프로세스들 중 실행 시간이 가장 짧은 프로세스부터 우선적으로 처리하는 방법을 의미한다. 실질적으로, 이 방법은 CPU의 스케줄링 알고리즘으로 널리 채택되어 있다.

---

특징

　이 개념은 평균 대기 시간 및 반환 시간의 최소화에 효과적이다. 또한, 이 방법은 시스템의 응답 시간 향상에 기여한다. 평균 대기 시간을 최소화하는 것이 이 알고리즘의 주요 목표이기 때문에, 대기 시간을 가능한 한 최소화하는 방법을 효율적으로 구현할 수 있다.

 

　하지만, 이 알고리즘은 프로세스의 실행 시간을 미리 알아야만 하는 제약사항을 갖고 있다. 이는 실시간 시스템에서 어려운 경우가 많다. 또한, 실행 시간이 긴 프로세스는 대기열에서 계속해서 밀려나는 현상, 즉 '기아(starvation)' 현상이 발생할 수 있으며, 이는 해당 프로세스가 무한정 대기하게 되는 문제를 야기할 수 있다. 이를 해결하기 위해 최단 작업 우선 스케줄링 알고리즘과 연계하여 사용되는 여러 기법들이 존재한다는 것까지 체크해 두고 넘어가자.

---

구현

　은행 창구에서 대기하고 있는 상황을 상상해보자. 이 은행에는 단 하나의 창구만이 있고, 대기열에는 총 8명의 고객이 차례를 기다리고 있다고 가정해 보자. 각 고객의 업무 처리 시간을 A라고 표현한다면, 고객별로 업무 처리 시간 A가 다르게 정해져 있다.

 

사람 P에 대한 업무 처리 시간 A

 

　이때 각 고객이 기다려야 하는 시간을 W라고 정의하자. 특정 고객 i가 기다려야 하는 시간, 즉 W_i는 그 이전 고객인 i-1번 째 고객의 업무 처리 시간 A_i-1까지의 누적 시간에 의해 결정된다. 이렇게 각 고객의 대기 시간 W는 이전 고객들의 업무 처리 시간을 순차적으로 더해가며 다음과 같이 계산된다.

 

 

　여기서 최단 작업 우선 스케줄링을 적용해 보자.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

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

	for (int i = 1; i < service_time.size(); ++i)
		W[i] = W[i - 1] + service_time[i - 1];

	return W;
}

　사람 P에 대한 대기 시간을 계산하는 compute_waiting_time() 함수다. W라는 벡터를 생성하여 누적합 개념을 이용해 W를 초기화시켜 주었다.

 

template <typename T>
void print(std::vector<T>& v, std::string name)
{
	std::cout << "- " << name << " time: ";
	for (const auto& val : v)
		std::cout << val << ' ';
	std::cout << "\n";
}

　벡터의 있는 내용을 꺼내서 출력하는 print() 함수다. 여기서 어떤 벡터를 꺼내는지 이름을 name으로 받아왔다.

 

template <typename T>
void scheduling(std::vector<T>& service_time)
{
	auto waiting_time = compute_waiting_time<int>(service_time);

	print(service_time, "process");
	print(waiting_time, "waiting");

	auto avg = std::accumulate(waiting_time.begin(),
		waiting_time.end(), 0.0) / waiting_time.size();

	std::cout << "- avg waiting time: " << avg << "\n";
}

　마지막으로 스케줄링을 적용하는 scheduing() 함수다. 대기 시간 wating_time을 compute_waiting_time()으로 받아와 업무 처리 시간과 대기 시간을 출력하게 작성하였다. 여기서 얼마나 개선되었는지 확인하기 위해 리듀스 연산을 하여 avg로 초기화 후 출력까지 하였다.

 

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

	std::cout << "------------before------------" << "\n";
	scheduling<int>(service_time);

	std::sort(service_time.begin(), service_time.end());
	std::cout << "\n";

	std::cout << "------------after------------" << "\n";
	scheduling<int>(service_time);
}

실행 결과, 대기열 순서를 조정한 후에 성능이 거의 두 배 향상되었다.

 

총합본

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

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

	for (int i = 1; i < service_time.size(); ++i)
		W[i] = W[i - 1] + service_time[i - 1];

	return W;
}

template <typename T>
void print(std::vector<T>& v, std::string name)
{
	std::cout << "- " << name << " time: ";
	for (const auto& val : v)
		std::cout << val << ' ';
	std::cout << "\n";
}

template <typename T>
void scheduling(std::vector<T>& service_time)
{
	auto waiting_time = compute_waiting_time<int>(service_time);

	print(service_time, "process");
	print(waiting_time, "waiting");

	auto avg = std::accumulate(waiting_time.begin(),
		waiting_time.end(), 0.0) / waiting_time.size();

	std::cout << "- avg waiting time: " << avg << "\n";
}

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

	std::cout << "------------before------------" << "\n";
	scheduling<int>(service_time);

	std::sort(service_time.begin(), service_time.end());
	std::cout << "\n";

	std::cout << "------------after------------" << "\n";
	scheduling<int>(service_time);
}

---

요약

그리디 알고리즘
1. 정의: 매 순간 최선의 선택을 하는 방법론적 알고리즘
2. 특징
　a. 각 단계에서 로컬 최적의 선택
　b. 선택이 불가역적: 이전의 선택이 이후의 선택에 영향을 주지 않음
3. 장점
　a. 간단하고 이해하기 쉬움
　b. 실행 시간이 빠름
4. 단점
　a. 문제가 그리디 속성을 가져야만 함
　b. 항상 최적의 해를 보장하지 않음
　c. 이전의 선택을 수정할 수 없음

최단 작업 우선 스케줄링
1. 정의: 대기 중인 프로세스 중애서 실행 시간이 짧은 프로세스부터 처리하는 방식
2. 장점
　a. 평균 대기 시간과 반환 시간 최적화에 효과적
　b. 시스텝 응답 시간 개선
3. 단점
　a. 프로세스 실행 시간을 미리 알아야 함
　b. 기아 문제 발생 가능성 존재