그리디 알고리즘 - 최단 작업 우선 스케줄링

그리디 알고리즘

 

 

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

즉, 그리디 방법은 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식이다.

예를 들어, 네비게이션이 인천국제공항에서 강남역까지 차로 이동하는 최단 경로를 보여주는 것 처럼 말이다.

이 경로상에 있는 임의의 두 지점을 선택할 경우,

이 두 지점의 최단 이동 거리는 처음에 구한 전체 최단 경로를 따라 이동함으로써 구할 수 있다.

전체 최단 경로는 사실상

이 경로상에 존재하는 다수의 지점 사이를 최단 거리 경로로 모두 연결시켜 놓은 것이라고 볼 수 있다.

그러므로 어느 두 지점 사이의 최단 경로를 구하기 위하여 다음과 같은 방법을 사용할 수 있다.

즉, 출발 지점에서 아직 방문하지 않은 가장 가까운 지점까지의 경로를 찾고,

이를 목적 지점에 다다를 때까지 반복하는 것이다.

 

이 방법이 구글 지도 또는 빙 지도 같은 사용 소프트웨어에서 사용되는

다익스트라 최단 경로 알고리즘의 기본 개념이다.

 

해당 글에서는 주어진 문제가 그리디 방식을 사용하기에 적합한지 판단하기 위해

사용되는 최적 부분 구조 속성과 그리디 선택 속성에 대해 알아볼 것이다.

그리고 주어진 문제가 이 두가지 속성을 가지고 있을 경우,

그리디 방법에 의해 올바른 결과를 얻을 수 있다는 점을 알게 될 것이다.

또한 실제로 그리디 솔루션에 제공되고 있는 몇몇 예제를 살펴볼 것이다.

 

 

 

기본적인 그리디 알고리즘

 

 그리디 방식으로 해결할 수 있는 대표적인 두 문제인 최단 작업 우선 스케줄링과

분할 가능 배낭 문제에 대하여 살펴보자.

 

최단 작업 우선 스케줄링

 

 은행 창구에서 줄을 서서 순서를 기다리는 사람들이 있다.

하필이면 은행이 바쁜 날인지, 하나의 창구에서만 업무를 보고 있으며,

대기열에 N명의 사람이 대기하고 있다.

이들은 서로 다른 용무로 방문했기 때문에 일 처리에 필요한 시간은 사람들마다 서로 다르다.

대기열에 기다리고 있던 모든 사람이 매우 합리적이어서 평균 대기 시간이 최소화될 수 있도록

대기 순서를 다시 정하는 것에 동의하였다.

그래서 이제 대기 순서를 어떻게 바꿔야 하는지를 결정해야 한다.

 

이 문제를 좀 더 쉽게 이해하기 위해 예를 하나 들어보겠다.

P[i]는 i번째 사람을 나타내고,

A[i]는 P[i]의 일 처리 시간, W[i]는 P[i]가 기다려야 하는 시간을 나타낸다.

창구에서 가까운 사람이 먼저 일을 처리할 수 있으므로 첫 번째 사람 P[0]의 대기 시간은 A[0] = 0이다.

대기열에서 두 번째에 있는 사람은

첫 번째 사람의 일 처리 시간만큼 기다려야 하기 때문에 W[0] = 8 이라면, A[1] = 8 이다. 

비슷한 방식으로 i번째 사람은 첫 번째 사람부터

i - 1번째 사람까지의 일 처리 시간의 합만큼 대기 시간이 필요하다.

 

이 문제의 해답을 구하는 방식은 다음과 같다.

평균 대기 시간을 최소화하는 것이 목표이기 때문에

가능한 많은 사람의 대기 시간을 줄일 수 있는 방법을 찾아야 한다.

모든 사람의 대기 시간을 줄이려면 일 처리가 가장 빨리 끝나는 사람을 맨 앞에 세워야 한다.

이러한 방식을 반복하면 다음과 같아진다.

 

 

 

연습 문제 : 최단 작업 우선 스케줄링

 

 

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


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

    for (auto i = 1; i < service_times.size(); i++)
    {
        W[i] = W[i - 1] + service_times[i - 1];
    }

    return W;
}

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

template<typename T>
void compute_and_print_wating_times(std::vector<T>& service_times)
{
    auto waiting_times = compute_wating_times<int>(service_times);

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

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

    auto ave_wating_times = std::accumulate(waiting_times.begin(), waiting_times.end(), 0.0) / waiting_times.size();

    std::cout << " - 평균 대기 시간 : " << ave_wating_times;

    std::cout << std::endl;

}

 

 

 

 

 

 

 

 

 

 

 

 

그리디 관련 문제

https://school.programmers.co.kr/learn/courses/30/parts/12244

프로그래머스

 

 

해당 게시글은 코딩 테스트를 위한 자료 구조와 알고리즘 with C++을

기반으로 제작되었습니다.