서로 다른 여러 작업(job) 목록이 주어지며, 각 작업에는 시작 시간, 종료 시간, 그리고 수행 시 얻을 수 있는 수익(profit)이 함께 표시되어 있습니다. 이 문제의 목표는 서로 시간이 겹치지 않는 작업들의 부분 집합을 찾아 총 수익을 최대화하는 것입니다.
이 알고리즘은 동적 계획법(Dynamic Programming)에 기반을 두고 있습니다. 하위 문제의 결과를 테이블에 저장해 둔 뒤, 저장된 값을 재활용하면서 전체 문제를 상향식(bottom-up) 방식으로 해결합니다.
기본 구현의 시간 복잡도는 O(n²)입니다. 다만, 이진 탐색(binary search)을 활용해 현재 작업과 충돌하지 않는 작업을 빠르게 찾도록 개선하면 시간 복잡도를 O(n log n)까지 줄일 수 있습니다.
핵심 아이디어
작업을 종료 시간 기준으로 오름차순 정렬한 후, 각 작업 i에 대해 다음 두 가지 경우 중 더 큰 값을 선택합니다.
- 현재 작업을 포함하는 경우: 현재 작업의 수익 + 현재 작업과 겹치지 않는 마지막 작업까지의 최대 수익
- 현재 작업을 포함하지 않는 경우: 바로 앞 작업(i-1)까지의 최대 수익
점화식으로 표현하면 다음과 같습니다.
table[i] = max(jobList[i].profit + table[nonConflict], table[i-1])
입력 및 출력
입력:
각 작업의 시작 시간, 종료 시간, 수익을 행렬 형태로 입력받습니다. 아래 예시에는 총 4개의 작업이 있습니다.
3 5 25
1 2 50
6 15 75
2 100 100
출력:
최대 수익은 150입니다.
가능한 작업 조합은 (작업 2, 작업 4) 또는 (작업 2, 작업 1, 작업 3)이며, 두 경우 모두 최대 수익은 150입니다.
알고리즘
findMaxProfit(jobList, n)
입력: 작업 목록과 작업의 개수 n
출력: 작업들을 통해 얻을 수 있는 최대 수익
시작
작업 목록을 종료 시간 기준으로 정렬한다
결과를 저장할 테이블을 정의한다
table[0] := jobList[0].profit
for i := 1 to n-1, do
addProfit := jobList[i].profit
nonConflict := 현재 작업과 충돌하지 않는 직전 작업을 찾는다
if 충돌하지 않는 작업이 존재하면, then
addProfit := addProfit + table[nonConflict]
if addProfit > table[i - 1], then
table[i] := addProfit
else
table[i] := table[i-1]
done
result := table[n-1]
return result
끝
C++ 구현 예제
#include <iostream>
#include <algorithm>
using namespace std;
struct Job {
int start, end, profit;
};
bool comp(Job job1, Job job2) {
return (job1.end < job2.end);
}
// jobList[i]와 시간이 겹치지 않는 마지막 작업의 인덱스를 반환
int nonConflictJob(Job jobList[], int i) {
for (int j=i-1; j>=0; j--) {
if (jobList[j].end <= jobList[i].start)
return j;
}
return -1;
}
int findMaxProfit(Job jobList[], int n) {
sort(jobList, jobList+n, comp); // 종료 시간 기준으로 작업 정렬
int *table = new int[n]; // 최대 수익을 저장할 테이블 생성
table[0] = jobList[0].profit;
for (int i=1; i<n; i++) {
// 현재 작업을 포함하는 경우의 수익 계산
int addProfit = jobList[i].profit;
int l = nonConflictJob(jobList, i);
if (l != -1)
addProfit += table[l];
// 포함하는 경우와 포함하지 않는 경우 중 최댓값 선택
table[i] = (addProfit > table[i-1]) ? addProfit : table[i-1];
}
int result = table[n-1];
delete[] table; // 메모리 해제
return result;
}
int main() {
Job jobList[] = {
{3, 5, 25},
{1, 2, 50},
{6, 15, 75},
{2, 100, 100}
};
int n = 4;
cout << "The maximum profit: " << findMaxProfit(jobList, n);
return 0;
}
실행 결과
The maximum profit: 150
복잡도 분석
시간 복잡도: 위 구현에서는 충돌하지 않는 작업을 선형 탐색으로 찾기 때문에 전체 시간 복잡도는 O(n²)입니다. 정렬된 상태를 활용해 이진 탐색으로 충돌하지 않는 작업을 찾으면 O(n log n)으로 개선할 수 있습니다.
공간 복잡도: 하위 문제의 결과를 저장하기 위해 크기 n의 테이블이 필요하므로 O(n)입니다.