문제 개요
N개의 작업 목록이 주어지며, 각 작업은 다음 세 가지 정보를 가지고 있습니다.
시작 시간(Start Time): 작업이 시작되는 시점
종료 시간(Finish Time): 작업이 끝나는 시점
수익(Profit): 작업 완료 시 얻는 이익
구하고자 하는 답은, 선택한 작업들끼리 실행 시간이 서로 겹치지 않으면서 수익의 총합이 최대가 되는 작업 부분 집합입니다.
예를 들어 입력이 N = 4, J = {{2, 3, 55}, {4, 6, 25}, {7, 20, 150}, {3, 150, 250}}이라면 결과는 [(2, 3, 55), (3, 150, 250)]이며, 최적 수익은 305가 됩니다.
풀이 접근 방법
이 문제는 동적 계획법(Dynamic Programming)과 이진 탐색(Binary Search)을 함께 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 작업을 차례대로 살펴보면서 “이 작업을 포함했을 때의 수익”과 “포함하지 않았을 때의 기존 최적 수익”을 비교해 더 큰 값을 테이블에 누적하는 것입니다.
1단계 — 충돌하지 않는 직전 작업 찾기(find_no_conflict)
현재 작업과 시간이 겹치지 않는, 즉 종료 시간이 현재 작업의 시작 시간 이하인 작업 중 가장 늦은 작업을 이진 탐색으로 찾습니다.
left := 0, right := index - 1로 초기화합니다.
left <= right인 동안 다음을 반복합니다.
mid := (left + right) / 2
jobs[mid].finish <= jobs[index].start라면:
jobs[mid + 1].finish <= jobs[index].start이면 left := mid + 1
그렇지 않으면 mid를 반환합니다.
그 외의 경우에는 right := mid - 1
조건을 만족하는 작업이 없으면 -1을 반환합니다.
2단계 — DP 테이블 구성
메인 로직에서는 다음 순서로 진행합니다.
job_list 배열을 종료 시간 기준으로 정렬합니다.
작업별 최적 결과를 저장할 크기 n짜리 테이블(table)을 생성합니다.
table[0].value := job_list[0].profit으로 설정하고, table[0]에 첫 번째 작업을 추가합니다.
i를 1부터 n-1까지 증가시키며 다음을 반복합니다.
include_profit := job_list[i].profit
l := find_no_conflict(job_list, i)
l이 -1이 아니라면 include_profit := include_profit + table[l].value
include_profit > table[i - 1].value라면:
table[i].value := include_profit
table[i].job := table[l].job에 job_list[i]를 추가한 목록
그렇지 않으면 table[i] := table[i - 1]
테이블에 기록된 작업 목록을 출력합니다.
최적 수익(Optimal Profit) := table[n - 1].value를 출력합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Job {
public:
int start, finish, profit;
};
struct job_with_weight {
vector<Job> job;
int value;
};
bool jobComparator(Job s1, Job s2) {
return (s1.finish < s2.finish);
}
int find_no_conflict(Job jobs[], int index) {
int left = 0, right = index - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (jobs[mid].finish <= jobs[index].start) {
if (jobs[mid + 1].finish <= jobs[index].start)
left = mid + 1;
else
return mid;
}
else
right = mid - 1;
}
return -1;
}
int get_max_profit(Job job_list[], int n) {
sort(job_list, job_list + n, jobComparator);
job_with_weight table[n];
table[0].value = job_list[0].profit;
table[0].job.push_back(job_list[0]);
for (int i = 1; i < n; i++) {
int include_profit = job_list[i].profit;
int l = find_no_conflict(job_list, i);
if (l != - 1)
include_profit += table[l].value;
if (include_profit > table[i - 1].value){
table[i].value = include_profit;
table[i].job = table[l].job;
table[i].job.push_back(job_list[i]);
}
else
table[i] = table[i - 1];
}
cout << "[";
for (int i=0; i<table[n-1].job.size(); i++) {
Job j = table[n-1].job[i];
cout << "(" << j.start << ", " << j.finish << ", " << j.profit << "),";
}
cout << "]\\nOptimal profit: " << table[n - 1].value;
}
int main() {
Job arr[] = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}};
int n = sizeof(arr)/sizeof(arr[0]);
get_max_profit(arr, n);
}
실행 결과
입력
{{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}
출력
[(2, 3, 55),(3, 150, 250)] Optimal profit: 305
시간 복잡도 분석
작업 목록을 정렬하는 데 O(n log n)이 필요하고, 각 작업마다 충돌 여부를 확인하는 이진 탐색에 O(log n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 모든 부분 집합을 일일이 검사하는 완전 탐색 방식(O(2^n))에 비해 성능이 크게 향상됩니다.