가중 구간 스케줄링은 각 작업에 시작 시각, 종료 시각, 보상 또는 가중치가 있고 서로 겹치지 않는 작업만 골라 가중치 합을 최대화하는 문제입니다. 종료 시각이 빠른 순서로 작업을 정렬하면 “현재 작업을 넣을 때 어디까지의 최적 결과를 재사용할 수 있는가”가 한 인덱스로 정리됩니다. 그 인덱스가 p(j): 작업 j와 겹치지 않는, 가장 뒤의 predecessor입니다. 이후 점화식은 현재 작업을 선택하는 경우와 건너뛰는 경우를 비교합니다.
이 문제에서 중요한 것은 “가장 빨리 끝나는 작업을 고르면 된다”는 무가중치 활동 선택 문제와 구분하는 것입니다. 보상이 다르면 짧은 작업 하나가 긴 고보상 작업을 방해할 수 있으므로 단순 탐욕법이 일반적으로 최적을 보장하지 않습니다.
입력 모델과 종료 시각 정렬
작업을 (start, finish, weight)로 두고, 겹치지 않는 조건을 finish_i ≤ start_j로 정하겠습니다. 종료 시각과 시작 시각이 같으면 서로 맞닿아도 허용하는 반개방 구간 또는 호환 정책입니다. 만약 시간 구간을 양끝 포함으로 해 finish_i < start_j만 허용한다면 이진 탐색 비교자를 바꿔야 합니다. ≤와 <는 구현의 사소한 차이가 아니라 선택 가능한 스케줄을 바꾸는 문제 계약입니다.
작업을 finish 오름차순으로 1..n에 재배열합니다. 같은 finish의 tie-break는 start, 원래 ID 등 결정적인 규칙으로 고정할 수 있지만, 점화식의 값은 finish 정렬이 유지되는 한 동일한 최적값입니다. 정렬 이후의 인덱스와 입력 원래 ID를 함께 저장해야 복원 결과를 사용자에게 원래 작업으로 돌려줄 수 있습니다.
다음 예제를 사용하겠습니다.
| 정렬 인덱스 j | 구간 (start, finish) | weight | p(j) |
|---|---|---|---|
| 1 | (1, 3) | 5 | 0 |
| 2 | (2, 5) | 6 | 0 |
| 3 | (4, 6) | 5 | 1 |
| 4 | (6, 7) | 4 | 3 |
| 5 | (5, 9) | 7 | 2 |
| 6 | (8, 10) | 3 | 4 |
작업 3의 시작은 4이므로 finish가 4 이하인 마지막 작업은 1입니다. 작업 4의 시작은 6이고 finish가 6 이하인 작업 3이 predecessor입니다. 작업 5의 시작은 5라서 finish 5인 작업 2까지가 호환되고, 작업 6의 시작은 8이라 finish 7인 작업 4가 마지막 호환 작업입니다.
predecessor의 의미와 이진 탐색
p(j)는 “j보다 앞에 있는 아무 작업”이 아니라, finish-time 정렬에서 finish[i] ≤ start[j]를 만족하는 가장 큰 i입니다. 이전 구간의 시작 시각으로 비교하면 안 됩니다. j와 겹치는지는 j가 언제 시작했는지와 이전 작업이 언제 끝났는지의 관계로 결정되기 때문입니다.
finish 배열 [3,5,6,7,9,10]에서 작업 5 (5,9,7)의 predecessor를 찾는다면 upper_bound(finish, 5) - 1을 사용해 인덱스 2, 즉 (2,5,6)을 얻습니다. finish < 5를 찾는 lower-bound 정책을 사용하면 작업 2를 제외하게 되어 1로 잘못 내려갈 수 있습니다. 반대로 끝나는 시각과 시작 시각이 같은 작업을 겹친다고 정의했다면 strict 비교가 맞습니다.
그림을 글로 읽기
- 작업 5: (5,9), w=7: 현재 선택 후보 · start = 5
- prefix 1..2: finish 3, 5 · p(5) = 2
- 작업 3 이후: finish 6 이상 · 작업 5와 겹침
- OPT(2): 앞 prefix의 최적값 · 선택 또는 skip
- 작업 5: (5,9), w=7 → prefix 1..2: finish ≤ start
- 작업 5: (5,9), w=7 → 작업 3 이후: finish > start
- prefix 1..2 → OPT(2): 재사용
실제 코드에서는 finish가 정렬되어 있고 start[j]가 숫자로 비교 가능한지 먼저 검사합니다. 시각이 문자열이면 사전순 정렬이 실제 시간순과 다를 수 있으므로 parsing/정규화를 앞단에서 끝냅니다. p(j)를 매 질의 선형 탐색하면 DP 값은 맞아도 전체 비용이 O(n²)가 되므로, 정렬 후 이진 탐색을 이용해 O(n log n) 전처리를 유지합니다.
선택·비선택 점화식
OPT(j)를 정렬된 첫 j개 작업만 사용했을 때 얻을 수 있는 최대 가중치로 정의합니다. 최적 스케줄에서 j를 선택했다면 j와 호환되는 앞 prefix만 함께 선택할 수 있으므로 그 후보는 weight[j] + OPT(p(j))입니다. j를 선택하지 않았다면 첫 j-1개에 대한 최적값 OPT(j-1)입니다. 따라서
OPT(0) = 0
OPT(j) = max(weight[j] + OPT(p(j)), OPT(j-1))
앞 예제의 중간 값은 다음과 같습니다.
| j | 선택 후보 w[j]+OPT(p(j)) |
건너뛰기 OPT(j-1) |
OPT(j) | 결정 |
|---|---|---|---|---|
| 0 | - | - | 0 | - |
| 1 | 5+0=5 | 0 | 5 | 1 선택 |
| 2 | 6+0=6 | 5 | 6 | 2 선택 |
| 3 | 5+5=10 | 6 | 10 | 1,3 |
| 4 | 4+10=14 | 10 | 14 | 1,3,4 |
| 5 | 7+6=13 | 14 | 14 | 5 건너뜀 |
| 6 | 3+14=17 | 14 | 17 | 1,3,4,6 |
작업 5의 가중치가 7이어도 OPT(4)=14를 넘지 못하므로 마지막 작업을 항상 넣으면 안 됩니다. 이 표는 “마지막 작업이 최적해에 반드시 들어간다”는 오개념을 반례로 보여 줍니다. 음수 가중치를 허용한다면 OPT(0)=0과 skip 후보가 음수 작업을 자동으로 거부한다는 의미도 명시해야 합니다. 모든 작업을 반드시 하나 이상 골라야 하는 별도 계약이면 초기값과 불가능 sentinel이 달라집니다.
표 계산과 복원
값만 필요하면 OPT 배열과 p 배열을 보관합니다. 실제 작업을 복원하려면 j=n에서 시작해 두 후보를 비교합니다. 선택 후보가 skip 후보보다 크면 j를 결과에 넣고 j=p(j)로 점프합니다. 그렇지 않으면 j를 j-1로 줄입니다. 동률에서는 예를 들어 skip을 우선한다고 고정하면 출력이 결정적이며, 선택을 우선하면 다른 최적 스케줄이 나올 수 있습니다. 두 결과가 모두 유효하다는 것과 동일한 출력이 나와야 한다는 것은 별개의 계약입니다.
reconstruct(j):
chosen = []
while j > 0:
take = weight[j] + OPT[p[j]]
skip = OPT[j-1]
if take > skip: # tie는 skip 우선 정책
chosen.push(j)
j = p[j]
else:
j = j - 1
reverse(chosen)
return chosen
앞 표에서 j=6은 17 대 14라 6을 넣고 j=4로 갑니다. j=4는 14 대 10이라 4를 넣고 j=3으로, j=3은 10 대 6이라 3을 넣고 j=1으로 갑니다. j=1을 넣고 0에 도착하면 [1,3,4,6]이 복원됩니다. j=p(j) 대신 무조건 j-1로 점프하면 작업 j를 선택했다는 사실을 잃고, 겹치는 작업을 다시 복원할 수 있습니다.
parent 비트를 미리 저장하면 복원 시 비교를 다시 하지 않아도 됩니다. 다만 값만 저장하는 구현에서도 p와 weight를 통해 후보를 재계산할 수 있으므로 parent는 시간과 메모리의 선택입니다. 원래 작업 ID, 같은 weight의 tie 정책, 반환 순서를 함께 저장하지 않으면 최댓값은 맞아도 사용자에게 전달할 스케줄이 불완전합니다.
정확성 논리와 경계
점화식의 정확성은 최적해를 j를 포함하는 경우와 포함하지 않는 경우로 나누는 데서 나옵니다. j를 포함하지 않으면 j-1 prefix의 어떤 스케줄이든 가능하고 최댓값은 OPT(j-1)입니다. j를 포함하면 j와 겹치는 작업을 고를 수 없으므로 나머지는 정확히 1..p(j) 안에 있고, 그 중 최적은 OPT(p(j))입니다. 두 경우를 모두 비교하므로 하나를 빠뜨리지 않습니다.
정렬이 끝나는 시간이 아니라 시작 시간 기준으로 되어 있거나, p의 비교자가 정렬 정책과 다르면 이 분할이 깨집니다. 구간이 열린 끝인지 닫힌 끝인지 혼용해 finish=5,start=5를 한 곳에서는 호환, 다른 곳에서는 충돌로 처리하는 것도 같은 종류의 오류입니다. 가중치가 매우 커질 수 있으면 합산 자료형 overflow를 점검하고, 음수·빈 입력·동일 구간·동률을 테스트해야 합니다.
비용과 대안
finish 정렬이 O(n log n), 각 predecessor 이진 탐색이 O(n log n), 표 계산과 복원이 O(n)이므로 전체는 O(n log n) 시간입니다. OPT와 p, 정렬된 작업 배열을 저장하는 공간은 O(n)입니다. 작업이 이미 finish 순서로 정렬되어 있거나 predecessor를 외부에서 제공하면 정렬 비용을 줄일 수 있지만, 입력이 정렬되어 있다는 계약을 검증해야 합니다.
가중치가 모두 같고 목적이 작업 개수라면 활동 선택의 탐욕 구조가 생길 수 있지만, 가중치가 임의이면 이 DP가 안전한 일반 해법입니다. 작업 간에 자원 종류, 인력 수, 전환 비용이 추가되면 상태가 단순한 prefix 하나로 충분하지 않을 수 있습니다. 겹침 외 제약이 늘어날 때마다 “같은 j prefix에서 미래 가능성이 정말 같나”를 다시 확인해야 합니다.
검증 절차와 참고 범위
작은 n에서는 모든 부분집합을 열거해 겹침이 없는지 확인하고 weight 합의 최대를 구해 DP와 비교합니다. 각 복원 결과에 대해 정렬된 인접 작업들이 finish_prev ≤ start_next인지, 합이 OPT(n)인지, 같은 작업이 두 번 들어가지 않았는지 확인합니다. 동률 정책은 값 비교와 독립적으로 테스트해 여러 최적 해 중 하나만 결정적으로 반환하는지 봅니다.
- Introduction to Algorithms, 4th ed. — MIT Press, 4th edition, 2022. 가중 구간 스케줄링의 predecessor와 include/exclude DP를 다루는 알고리즘 참고서로 기록되어 있습니다. 공개 landing page에는 장·쪽 단위 본문 excerpt가 없으므로 세부 페이지 인용까지 했다고 주장하지 않습니다.
- 동적 계획법의 상태와 탐욕 반례 — 저장소 노트의 상태 충분성·복원·sentinel 주의를 대조했습니다.
- 위 표와 숫자 trace는 설명용 손계산입니다. 이 batch에서는 구현을 실행해 성공한 결과나 특정 언어의 정렬 안정성을 보고하지 않습니다.