기한이 있는 작업 순서 문제 – 그리디 알고리즘으로 이익 최대화하기

문제 개요

기한이 있는 작업 순서(Job Sequencing with Deadlines) 문제는 그리디 알고리즘의 대표적인 응용 사례입니다. 작업 목록이 주어지며, 각 작업에는 고유 ID, 마감 기한(deadline), 그리고 완료 시 얻을 수 있는 이익(profit)이 함께 제공됩니다.

모든 작업은 하나의 시간 단위를 소요하므로 작업의 최소 마감 기한은 1입니다. 한 번에 하나의 작업만 스케줄링할 수 있을 때, 어떤 순서로 작업을 배치해야 총 이익을 최대화할 수 있을까요?

접근 방법

가장 단순한 방법은 작업 집합의 모든 부분집합을 생성하고, 각 부분집합이 마감 기한 조건을 만족하는지(실현 가능 여부) 검사한 뒤, 실현 가능한 부분집합 중 최대 이익을 추적하는 것입니다.

하지만 실전에서는 그리디 알고리즘이 훨씬 효율적입니다. 핵심 아이디어는 다음과 같습니다.

작업을 이익 기준으로 내림차순 정렬합니다.
각 작업을 마감 기한 이내 시간 슬롯 중 가장 늦은 빈 슬롯에 배치합니다.
늦은 슬롯부터 채우면 앞쪽 슬롯이 비어 있게 되어, 다른 작업이 배치될 여지가 생깁니다.

이 알고리즘의 시간 복잡도는 O(n²)입니다.

입력 및 출력

입력:
작업 ID, 마감 기한, 이익으로 구성된 작업 목록과 작업 수 n.
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
출력:
최대 이익을 내는 작업 순서: c a e

알고리즘

jobSequence(jobList, n)

입력 − 작업 목록과 목록에 포함된 작업의 수

출력 − 작업이 처리되는 순서

시작
    jobList의 작업들을 이익 기준으로 정렬
    작업 순서를 저장할 jobSequence 리스트와 빈 시간 슬롯을 추적할 slot 배열 생성
    처음에 모든 슬롯을 비어 있는 상태로 초기화
    주어진 모든 작업 i에 대해 반복
        목록 끝에서부터 각 위치 j에 대해 반복
            slot[j]가 비어 있다면
                jobSequence[j] := i
                slot[j] := 채움
                반복 종료(break)
        완료
    완료

    채워진 모든 슬롯 i에 대해
        jobList[jobSequence[i]]를 사용해 해당 작업의 ID 출력
    완료
끝

C++ 구현 예제

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

struct Job {
    char id;
    int deadLine;
    int profit;
};

bool comp(Job j1, Job j2) {
    return (j1.profit > j2.profit);     // 이익 기준으로 작업 비교
}

int min(int a, int b) {
    return (a<b)?a:b;
}

void jobSequence(Job jobList[], int n) {
    sort(jobList, jobList+n, comp);     // 이익 기준으로 jobList 정렬

    int jobSeq[n];      // 결과(작업 순서)를 저장할 배열
    bool slot[n];       // 빈 시간 슬롯을 추적할 배열

    for (int i=0; i<n; i++)
        slot[i] = false; // 처음에 모든 슬롯은 비어 있음

    for (int i=0; i<n; i++) {     // 주어진 모든 작업에 대해
        for (int j=min(n, jobList[i].deadLine)-1; j>=0; j--) {   // 마지막 빈 슬롯부터 역순 탐색
            if (slot[j]==false) {
                jobSeq[j] = i;   // 작업을 순서에 추가
                slot[j] = true;  // 해당 슬롯을 점유 상태로 표시
                break;
            }
        }
    }

    for (int i=0; i<n; i++)
        if (slot[i])
            cout << jobList[jobSeq[i]].id << " ";     // 작업 순서 출력
}

int main() {
    Job jobList[] = {{'a',2,100}, {'b',1,19}, {'c',2,27},{'d',1,25},{'e',3,15}};
    int n = 5;
    cout << "Following is maximum profit sequence of job sequence: ";
    jobSequence(jobList, n);
}

실행 결과

Following is maximum profit sequence of job sequence: c a e

동작 원리 살펴보기

예제의 작업들을 이익 기준으로 내림차순 정렬하면 a(100), c(27), d(25), b(19), e(15) 순서가 됩니다.

a(마감 2): 슬롯 1(두 번째 시간)에 배치 → [_, a]
c(마감 2): 슬롯 1이 차 있어 슬롯 0(첫 번째 시간)에 배치 → [c, a]
d(마감 1): 슬롯 0이 이미 차 있어 배치 불가 → 건너뜀
b(마감 1): 슬롯 0이 차 있어 배치 불가 → 건너뜀
e(마감 3): 슬롯 2(세 번째 시간)에 배치 → [c, a, e]

따라서 최종 작업 순서는 c a e이며, 총 이익은 100 + 27 + 15 = 142가 됩니다.