2026-02-03 | 8 min read | 117 | 그리디 스케줄링 알고리즘

7-9. 그리디: Interval Scheduling (구간 스케줄링) - 심화

1. 구간 스케줄링 문제 복습

지난 포스트에서 다룬 구간 스케줄링(Interval Scheduling) 문제는, 주어진 일련의 구간(작업)들 중에서 서로 겹치지 않는 구간들을 최대한 많이 선택하는 문제입니다. 예를 들어, 회의실 사용 스케줄을 잡는다고 생각해 봅시다. 여러 개의 회의 요청이 들어왔고, 각 요청은 시작 시간과 종료 시간을 가지고 있습니다. 우리는 회의실을 최대한 효율적으로 사용하기 위해, 겹치지 않는 회의들을 최대한 많이 선택해야 합니다.

그리디(Greedy) 알고리즘을 사용하면 이 문제를 효과적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

종료 시간 기준 정렬: 모든 구간들을 종료 시간의 오름차순으로 정렬합니다.
선택: 정렬된 순서대로 각 구간을 확인하며, 현재 선택된 구간과 겹치지 않는 구간을 선택합니다.

이러한 그리디 전략은 최적해를 보장합니다. 즉, 가장 많은 수의 겹치지 않는 구간들을 선택할 수 있습니다.

2. 구간 스케줄링의 심화 문제: 가중치 구간 스케줄링

일반적인 구간 스케줄링 문제는 각 구간이 동일한 중요도를 가진다고 가정합니다. 그러나 현실 세계에서는 각 작업마다 가중치가 부여되는 경우가 많습니다. 예를 들어, 서로 다른 수익을 가져다주는 프로젝트들을 선택해야 하는 경우를 생각해 볼 수 있습니다. 이러한 경우, 단순히 겹치지 않는 구간의 개수를 최대화하는 것이 아니라, 선택된 구간들의 가중치의 합을 최대화하는 것이 목표가 됩니다. 이것이 가중치 구간 스케줄링(Weighted Interval Scheduling) 문제입니다.

1) 문제 정의

가중치 구간 스케줄링 문제는 다음과 같이 정의됩니다.

$n$개의 구간 $I_i = (s_i, f_i, w_i)$가 주어집니다. 여기서 $s_i$는 시작 시간, $f_i$는 종료 시간, $w_i$는 가중치를 나타냅니다.
두 구간 $I_i$와 $I_j$가 겹치지 않는다는 것은 $f_i \le s_j$ 또는 $f_j \le s_i$임을 의미합니다.
목표는 서로 겹치지 않는 구간들의 부분 집합을 선택하여, 선택된 구간들의 가중치 합을 최대화하는 것입니다.

2) 예시

다음과 같은 4개의 구간이 주어졌다고 가정해 봅시다.

구간	시작 시간	종료 시간	가중치
A	0	2	2
B	1	3	4
C	0	4	7
D	3	5	3

이 경우, 가중치 합을 최대화하는 최적의 선택은 구간 A와 D를 선택하는 것입니다. (가중치 합: 2 + 3 5) 또는 구간 B와 D를 선택하는 것입니다. (가중치 합: 4 + 3 7). 구간 C는 다른 구간과 겹치기 때문에, 단독으로 선택해야 합니다.

3. 가중치 구간 스케줄링 문제 해결 전략: 동적 계획법 (Dynamic Programming)

가중치 구간 스케줄링 문제는 그리디 알고리즘만으로는 해결할 수 없습니다. 종료 시간 순으로 정렬한 후, 그리디하게 구간을 선택하는 방식은 최적해를 보장하지 못합니다. 예를 들어, 위에 제시된 예시에서 종료 시간이 가장 빠른 구간 A를 먼저 선택하면, 구간 C를 선택할 수 없게 되어 최적해를 놓치게 됩니다.

가중치 구간 스케줄링 문제를 해결하기 위한 효과적인 방법은 동적 계획법(Dynamic Programming)입니다. 동적 계획법은 문제를 작은 하위 문제로 나누어 해결하고, 하위 문제의 해결 결과를 저장하여 중복 계산을 피하는 방식입니다.

1) 재귀적 구조 정의

동적 계획법을 적용하기 위해, 먼저 재귀적 구조를 정의해야 합니다.

구간들을 종료 시간 순으로 정렬합니다. (이전과 동일)
$p(j)$: 구간 $j$와 겹치지 않는, 구간 $j$ 이전의 가장 마지막 구간의 인덱스. 즉, 구간 $i$가 $j$와 겹치지 않으면서, 구간 $i$의 종료 시간이 구간 $j$의 시작 시간보다 작은 가장 큰 $i$입니다. (겹치는 구간이 없으면 $p(j) = 0$이 됩니다.)
OPT(j): 구간 $j$까지 고려했을 때, 선택된 구간들의 최대 가중치 합

OPT(j)는 다음과 같은 재귀적 관계를 통해 정의됩니다.

$$ OPT(j) = \max\begin{cases} w_j + OPT(p(j)) & \text{구간 } j \text{를 선택하는 경우} \\ OPT(j-1) & \text{구간 } j \text{를 선택하지 않는 경우} \end{cases} $$

구간 $j$를 선택하는 경우: 구간 $j$의 가중치 $w_j$를 더하고, 구간 $j$와 겹치지 않는 마지막 구간 $p(j)$까지의 최대 가중치 합 $OPT(p(j))$를 더합니다.
구간 $j$를 선택하지 않는 경우: 이전 구간들까지의 최대 가중치 합 $OPT(j-1)$을 사용합니다.

2) 예시를 통한 이해

위에서 제시한 예시를 다시 살펴보겠습니다.

구간	시작 시간	종료 시간	가중치
A (1)	0	2	2
B (2)	1	3	4
C (3)	0	4	7
D (4)	3	5	3

(괄호 안의 숫자는 편의상 구간의 인덱스입니다.)

종료 시간 순으로 정렬: 이미 종료 시간 순으로 정렬되어 있습니다.
p(j) 계산:
- $p(1) = 0$ (A와 겹치는 구간 없음)
- $p(2) = 0$ (B와 겹치는 구간 없음)
- $p(3) = 0$ (C와 겹치는 구간 없음)
- $p(4) = 2$ (D와 겹치지 않는 마지막 구간은 B)
OPT(j) 계산:
- OPT(0) = 0 (기저 사례: 구간 없음)
- OPT(1) max(2 + OPT(0), OPT(0)) max(2, 0) = 2 (구간 A 선택)
- OPT(2) max(4 + OPT(0), OPT(1)) max(4, 2) = 4 (구간 B 선택)
- OPT(3) max(7 + OPT(0), OPT(2)) max(7, 4) = 7 (구간 C 선택)
- OPT(4) max(3 + OPT(2), OPT(3)) max(3 + 4, 7) max(7, 7) 7 (구간 D 선택)

따라서, 최적의 가중치 합은 OPT(4) = 7이며, 선택된 구간은 B와 D이거나 C와 D입니다.

3) 동적 계획법 구현 (파이썬)

def weighted_interval_scheduling(intervals):
    """
    가중치 구간 스케줄링 문제 해결 (동적 계획법)

    Args:
        intervals: 각 구간의 정보를 담은 리스트.
                   각 구간은 (시작 시간, 종료 시간, 가중치) 형태의 튜플.

    Returns:
        최대 가중치 합.
    """

    # 1. 종료 시간 순으로 정렬
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)

    # 2. p(j) 계산
    def find_non_overlapping(j):
        for i in range(j - 1, -1, -1):
            if intervals[i][1] <= intervals[j][0]:
                return i
        return -1  # 겹치는 구간이 없으면 -1 반환

    p = [find_non_overlapping(j) for j in range(n)]

    # 3. OPT(j) 계산 (동적 계획법)
    opt = [0] * n
    opt[0] = intervals[0][2] # 첫 번째 구간 선택

    for j in range(1, n):
        include_j = intervals[j][2] # 현재 구간의 가중치
        if p[j] != -1:
          include_j += opt[p[j]]
        opt[j] = max(include_j, opt[j - 1])

    return opt[n - 1]

동적 계획법 코드 설명 아래

위 코드는 가중치 구간 스케줄링 문제를 동적 계획법으로 해결하는 파이썬 구현입니다.

intervals를 종료 시간 기준으로 정렬합니다.
find_non_overlapping 함수를 사용하여 각 구간 $j$에 대해 $p(j)$를 계산합니다.
opt 리스트를 사용하여 OPT(j) 값을 저장합니다.
반복문을 통해 $OPT(j)$ 값을 계산합니다. 구간 $j$를 선택하는 경우와 선택하지 않는 경우를 비교하여 최대값을 선택합니다.
최종적으로 opt[n-1]이 최적해를 반환합니다.

4. 응용 및 확장

가중치 구간 스케줄링 문제는 다양한 실제 문제에 적용될 수 있습니다.

프로젝트 스케줄링: 각 프로젝트의 시작 시간, 종료 시간, 예상 수익을 알고 있을 때, 겹치지 않는 프로젝트들을 선택하여 총 수익을 최대화하는 문제.
광고 캠페인 스케줄링: 각 광고 캠페인의 시작 시간, 종료 시간, 예상 노출 횟수(또는 수익)를 알고 있을 때, 광고 캠페인을 선택하여 최대 노출 횟수(또는 수익)를 달성하는 문제.
자원 할당 문제: 예를 들어, 서로 다른 작업(task)들이 특정 자원(resource)을 필요로 하고, 각 작업의 시작 시간, 종료 시간, 필요 자원량, 그리고 가치가 주어졌을 때, 자원 제약 내에서 가치 합을 최대화하는 문제. (이 경우, 가중치 외에 자원 제약 조건을 추가해야 합니다.)

1) 변형: 자원 제약 추가

가중치 구간 스케줄링 문제는 자원 제약 조건과 함께 확장될 수 있습니다. 예를 들어, 각 작업이 특정 양의 자원을 필요로 하고, 전체 자원 용량이 제한되어 있을 경우, 자원 제약 조건을 만족하면서 가중치 합을 최대화해야 합니다. 이 경우, 동적 계획법을 사용하여 해결할 수 있지만, 상태 공간이 더 복잡해집니다.

$$ OPT(j, r) = \max\begin{cases} w_j + OPT(p(j), r - res_j) & \text{구간 } j \text{를 선택하는 경우, } r \ge res_j \\ OPT(j-1, r) & \text{구간 } j \text{를 선택하지 않는 경우} \end{cases} $$

여기서 $OPT(j, r)$은 구간 $j$까지 고려했을 때, 사용된 자원이 $r$이하인 경우의 최대 가중치 합을 나타냅니다. $res_j$는 구간 $j$가 필요로 하는 자원 량입니다. 이러한 변형된 문제는 knapsack 문제와 유사한 방식으로 해결될 수 있습니다.

2) 추가적인 고려 사항

복잡도: 동적 계획법의 시간 복잡도는 $O(n \log n)$ (정렬) + $O(n^2)$ (OPT 계산) = $O(n^2)$입니다. 가중치가 정수이고, 가중치의 범위가 작을 경우 더 효율적인 알고리즘을 사용할 수도 있습니다.
실용적인 최적화: 실제 구현 시, 메모리 사용량을 줄이기 위해 opt 배열을 1차원 배열로 사용하는 등의 최적화를 고려할 수 있습니다.
근사 알고리즘: 입력 크기가 매우 크거나, 문제의 복잡도가 높은 경우, 근사 알고리즘을 사용하여 문제를 해결할 수 있습니다.

5. 주의사항 및 트러블슈팅

1) 종료 시간 순 정렬의 중요성

구간 스케줄링 문제를 해결할 때 가장 중요한 단계는 구간들을 종료 시간 순으로 정렬하는 것입니다. 정렬이 제대로 이루어지지 않으면, 그리디 알고리즘이나 동적 계획법 모두 최적해를 보장할 수 없습니다.

정렬 방법: sort() 함수를 사용할 때, key 매개변수를 사용하여 정렬 기준을 명확하게 지정해야 합니다. 예를 들어, intervals.sort(key=lambda x: x[1])은 각 구간의 종료 시간(두 번째 요소)을 기준으로 오름차순 정렬합니다.
예외 처리: 시작 시간과 종료 시간이 같은 구간이 있을 수 있습니다. 이러한 경우, 알고리즘이 올바르게 작동하도록 처리해야 합니다. 종료 시간이 같은 경우, 시작 시간을 기준으로 정렬하거나, 가중치가 높은 구간을 먼저 선택하는 등의 추가적인 기준을 적용할 수 있습니다.

2) p(j) 계산 오류

p(j)를 정확하게 계산하는 것이 동적 계획법의 핵심입니다. p(j)는 구간 $j$와 겹치지 않는, $j$ 이전의 가장 마지막 구간의 인덱스를 의미합니다.

겹침 판단: 두 구간이 겹치는지 여부를 판단하는 정확한 로직을 구현해야 합니다. 두 구간 $I_i = (s_i, f_i)$와 $I_j = (s_j, f_j)$가 겹치지 않으려면, $f_i \le s_j$ 또는 $f_j \le s_i$를 만족해야 합니다.
예외 처리: p(j)가 존재하지 않는 경우 (즉, 구간 $j$와 겹치지 않는 구간이 없는 경우), -1 또는 0과 같은 특수한 값을 반환하여 처리해야 합니다.

3) 동적 계획법 구현 오류

동적 계획법을 구현할 때, 재귀적 관계를 정확하게 코드로 옮기는 것이 중요합니다.

기저 사례: OPT(0)과 같은 기저 사례를 올바르게 정의하고 초기화해야 합니다.
재귀 관계: OPT(j)를 계산하는 재귀적 관계를 정확하게 구현해야 합니다. 구간 $j$를 선택하는 경우와 선택하지 않는 경우를 모두 고려해야 합니다.
배열 인덱스: 배열 인덱스에 접근할 때, 인덱스 범위를 벗어나지 않도록 주의해야 합니다.

6. 결론

가중치 구간 스케줄링 문제는 일반적인 구간 스케줄링 문제의 확장으로, 그리디 알고리즘으로는 해결할 수 없는 문제입니다. 동적 계획법을 사용하여 이 문제를 효과적으로 해결할 수 있으며, 다양한 실제 문제에 적용될 수 있습니다. 문제를 정확하게 이해하고, 재귀적 구조를 정의하며, 동적 계획법을 올바르게 구현하는 것이 중요합니다. 자원 제약 조건을 추가하는 등, 문제에 다양한 변형을 적용하여 더욱 현실적인 문제를 해결할 수도 있습니다.