2026-02-03 | 8 min read | 105 | 그리디 스케줄링 문제 해결

7-7. 그리디: 스케줄링 (Job Scheduling)

1. 작업 스케줄링 문제의 개요

작업 스케줄링(Job Scheduling)은 주어진 자원(resource)을 효율적으로 활용하기 위해, 특정 작업을 어떤 순서로, 언제 실행할지 결정하는 문제들을 총칭합니다. 이 문제는 컴퓨터 시스템, 운영 체제, 생산 관리, 프로젝트 관리 등 다양한 분야에서 나타납니다. 핵심 목표는 일반적으로 작업 완료 시간 최소화, 자원 활용 극대화, 비용 최소화 등입니다. 작업 스케줄링 문제는 그 자체로 매우 복잡하며, 다양한 제약 조건과 목표 함수를 가질 수 있습니다. 따라서 문제를 해결하기 위해 여러 가지 알고리즘과 기법들이 사용됩니다. 그리디 알고리즘은 이러한 작업 스케줄링 문제 중 일부 유형에 대해 효과적인 해결책을 제공할 수 있으며, 특히 최적해에 대한 근사해를 빠르게 찾을 수 있다는 장점을 가집니다.

작업 스케줄링 문제를 이해하기 위한 기본적인 용어들을 먼저 살펴보겠습니다.

작업 (Job): 수행해야 할 개별적인 작업 단위. 각 작업은 고유한 속성(예: 작업 시간, 마감 시간, 가중치 등)을 가질 수 있습니다.
자원 (Resource): 작업을 처리하는 데 필요한 것 (예: CPU, 메모리, 기계, 인력 등).
스케줄 (Schedule): 각 작업을 어떤 자원에서, 어떤 시간에 실행할지 결정하는 계획.
완료 시간 (Completion Time): 작업이 완료되는 시간.
마감 시간 (Deadline): 작업이 완료되어야 하는 시간.
지연 시간 (Lateness): 작업 완료 시간과 마감 시간의 차이 (완료 시간이 마감 시간보다 늦으면 양수).
가중치 (Weight): 작업의 중요도를 나타내는 값.

작업 스케줄링 문제는 NP-hard 문제인 경우가 많아, 규모가 커지면 최적해를 찾는 것이 매우 어렵습니다. 따라서, 그리디 알고리즘, 동적 계획법, 분기 한정법, 유전 알고리즘과 같은 다양한 접근 방식이 사용됩니다. 그리디 알고리즘은 각 단계에서 최적의 선택을 함으로써 전체적인 최적해에 근접하는 해를 찾는 데 유용합니다.

2. 그리디 알고리즘의 적용

그리디 알고리즘은 각 단계에서 현재 가장 좋아 보이는 선택을 하는 방식으로 문제를 해결합니다. 작업 스케줄링 문제에 그리디 알고리즘을 적용할 때는, 특정 기준(예: 마감 시간, 작업 시간, 가중치 등)을 기준으로 작업을 정렬하고, 정렬된 순서대로 작업을 스케줄에 추가합니다. 그리디 알고리즘은 모든 경우에 최적의 해를 보장하지는 않지만, 계산 복잡도가 낮아 효율적인 해를 빠르게 찾을 수 있다는 장점이 있습니다.

그리디 알고리즘을 적용할 때 고려해야 할 중요한 사항은 다음과 같습니다.

선택 기준 (Selection Criteria): 어떤 기준을 사용하여 각 단계에서 최적의 작업을 선택할 것인가? 마감 시간, 작업 시간, 가중치 등 문제의 특성에 따라 적절한 기준을 선택해야 합니다.
탐욕적 선택 속성 (Greedy Choice Property): 각 단계에서의 최적 선택이 전체 문제에 대한 최적해로 이어진다는 것을 증명할 수 있는가? 그리디 알고리즘이 최적해를 보장하지 않는 경우도 있으므로, 선택 기준의 적절성을 신중하게 판단해야 합니다.
최적 부분 구조 (Optimal Substructure): 문제의 최적해가 부분 문제의 최적해를 포함하는가? 만약 그렇다면, 그리디 알고리즘을 적용하여 효율적인 해결 방안을 찾을 수 있습니다.

작업 스케줄링 문제에 그리디 알고리즘을 적용하는 일반적인 단계는 다음과 같습니다.

문제 정의: 작업, 자원, 제약 조건, 목표 함수를 명확하게 정의합니다.
선택 기준 결정: 그리디 선택을 위한 기준을 설정합니다 (예: 마감 시간, 작업 시간 등).
작업 정렬: 선택 기준에 따라 작업을 정렬합니다.
스케줄 구성: 정렬된 순서대로 작업을 스케줄에 추가합니다. 각 작업을 추가할 때, 제약 조건을 만족하는지 확인합니다.
해 평가: 구성된 스케줄의 목표 함수 값을 계산하여 해를 평가합니다.

3. 작업 스케줄링 문제 유형 및 해결

작업 스케줄링 문제는 다양한 유형으로 분류할 수 있습니다. 각 유형에 따라 그리디 알고리즘의 적용 방법과 선택 기준이 달라집니다. 다음은 몇 가지 대표적인 유형과 해결 방법을 제시합니다.

1) 마감 시간 (Deadline)과 작업 시간 (Duration)을 고려한 스케줄링

가장 기본적인 유형 중 하나로, 각 작업에 대해 마감 시간과 작업 시간이 주어집니다. 목표는 모든 작업을 마감 시간 내에 완료하면서, 지연 시간을 최소화하는 것입니다.

문제 정의:
- $n$개의 작업
- 작업 $i$의 마감 시간: $d_i$
- 작업 $i$의 작업 시간: $t_i$
- 작업 $i$의 지연 시간: $l_i = \max(0, C_i - d_i)$, 여기서 $C_i$는 작업 $i$의 완료 시간
그리디 알고리즘 해결:
1. 마감 시간 기준 정렬: 모든 작업을 마감 시간 $(d_i)$에 따라 오름차순으로 정렬합니다.
2. 스케줄 구성: 정렬된 순서대로 각 작업을 스케줄에 추가합니다. 각 작업을 추가할 때, 현재 시점에서 작업 시간을 더하여 완료 시간을 계산합니다. 만약 완료 시간이 마감 시간을 초과하면, 지연 시간이 발생합니다.
선택 기준: 마감 시간 (deadline)

``` def schedule_jobs_by_deadline(jobs): """ 마감 시간 기준 작업 스케줄링 (지연 시간 최소화)

Args: jobs: 각 작업의 (작업시간, 마감시간) 튜플 리스트

Returns: 작업 스케줄 (작업 인덱스 리스트) """ # 1. 마감 시간 기준으로 작업 정렬 sorted_jobs = sorted([(i, job[0], job[1]) for i, job in enumerate(jobs)], key=lambda x: x[2]) # (index, duration, deadline)

schedule = [] current_time = 0

# 2. 스케줄 구성 for i, duration, deadline in sorted_jobs: if current_time + duration <= deadline: schedule.append(i) # 작업 추가 current_time += duration # else: 마감 시간 초과 - 지연 발생 (일반적으로 이 부분에서 다른 작업 고려)

return schedule ```

2) 작업 완료 시간 (Completion Time) 최소화

여러 개의 작업을 하나의 자원에서 처리할 때, 모든 작업의 완료 시간을 최소화하는 것이 목표인 문제입니다. 작업 시간만 주어지고 마감 시간은 없는 경우에 해당합니다.

문제 정의:
- $n$개의 작업
- 작업 $i$의 작업 시간: $t_i$
- 목표: $\text{Minimize} \sum_{i=1}^{n} C_i$, 여기서 $C_i$는 작업 $i$의 완료 시간
그리디 알고리즘 해결:
1. 작업 시간 기준 정렬: 모든 작업을 작업 시간 $(t_i)$에 따라 오름차순으로 정렬합니다.
2. 스케줄 구성: 정렬된 순서대로 작업을 순차적으로 실행합니다.

선택 기준: 작업 시간 (duration)

``` def minimize_completion_time(jobs): """ 작업 완료 시간 최소화

Args:
    jobs: 각 작업의 작업 시간 리스트

Returns:
    작업 스케줄 (작업 인덱스 리스트)
"""
# 1. 작업 시간 기준으로 작업 정렬
sorted_jobs = sorted([(i, job) for i, job in enumerate(jobs)], key=lambda x: x[1])  # (index, duration)

schedule = [job_index for job_index, _ in sorted_jobs]  # 작업 인덱스 순서대로 반환
return schedule

```

3) 가중치가 있는 작업 스케줄링

각 작업에 가중치가 부여되어, 가중치가 높은 작업을 먼저 처리하는 것이 목표인 문제입니다. 예를 들어, 작업의 중요도에 따라 가중치가 부여될 수 있습니다. 이 경우, 지연 시간을 최소화하는 것과 함께 가중치를 고려해야 합니다.

문제 정의:
- $n$개의 작업
- 작업 $i$의 마감 시간: $d_i$
- 작업 $i$의 가중치: $w_i$
- 작업 $i$의 지연 시간: $l_i$
- 목표: $\text{Maximize} \sum_{i=1}^{n} w_i \cdot \mathbb{I}(l_i = 0)$, 여기서 $\mathbb{I}$는 지연이 없는 경우 1, 그렇지 않은 경우 0을 반환하는 지시 함수
그리디 알고리즘 해결:
1. 가중치/마감 시간 기준 정렬: 가중치가 큰 작업을 먼저 처리하거나, 마감 시간이 빠른 작업을 먼저 처리하는 등 문제에 적합한 기준을 선택하여 작업을 정렬합니다. 가중치와 마감 시간을 모두 고려해야 하는 경우, 가중치/마감 시간 비율 (예: $w_i / d_i$)을 기준으로 정렬하는 방법을 사용할 수 있습니다.
2. 스케줄 구성: 정렬된 순서대로 작업을 스케줄에 추가합니다. 각 작업을 추가할 때, 지연 시간이 발생하지 않도록 합니다.
선택 기준: 가중치, 마감 시간, 혹은 가중치/마감 시간 비율.

4) 간격 분할 (Interval Partitioning)

간격 분할 문제는 서로 겹치지 않도록 일련의 간격을 최소한의 자원으로 처리하는 문제입니다. 예를 들어, 회의 시간표를 만들 때, 각 회의가 특정 시간에 시작하고 끝나며, 겹치는 회의는 같은 자원에서 처리할 수 없습니다.

문제 정의:
- $n$개의 간격 (각 간격은 시작 시간과 종료 시간을 가짐)
- 목표: 겹치지 않는 간격들을 최대한 많은 자원에 할당.
그리디 알고리즘 해결:
1. 종료 시간 기준 정렬: 모든 간격을 종료 시간에 따라 오름차순으로 정렬합니다.
2. 스케줄 구성: 정렬된 순서대로 간격을 선택하고, 현재 자원에서 처리할 수 있으면 할당합니다. 만약 현재 자원에서 처리할 수 없으면, 새로운 자원을 할당합니다.

선택 기준: 종료 시간

간격 분할 문제 시각화 예시

``` def interval_partitioning(intervals): """ 간격 분할 문제 (최소 자원 사용)

Args:
    intervals: 각 간격의 (시작 시간, 종료 시간) 튜플 리스트

Returns:
    각 간격에 할당된 자원 딕셔너리
"""
# 1. 종료 시간 기준으로 간격 정렬
sorted_intervals = sorted(intervals, key=lambda x: x[1])

resources = {}
resource_count = 0  # 필요한 자원의 수

# 2. 스케줄 구성
for interval in sorted_intervals:
    start_time, end_time = interval
    assigned = False  # 간격이 자원에 할당되었는지 여부

    # 기존 자원 확인
    for resource_id in range(resource_count):
        # 해당 자원의 마지막 작업의 종료 시간
        last_end_time = 0
        if resource_id in resources:
            if resources[resource_id]:
                last_end_time = resources[resource_id][-1][1]  # 마지막 작업 종료시간
        if start_time >= last_end_time:
            # 현재 간격을 자원에 할당
            if resource_id not in resources:
                resources[resource_id] = []
            resources[resource_id].append(interval)
            assigned = True
            break # 현재 자원에 할당 완료

    if not assigned:  # 새로운 자원 할당
        resources[resource_count] = [interval]
        resource_count += 1
return resources

```

4. 실전 문제 풀이 예시

다음은 코딩 테스트에서 자주 출제되는 작업 스케줄링 문제의 예시입니다.

문제:

n개의 작업이 주어집니다. 각 작업은 작업 시간 duration[i]와 마감 시간 deadline[i]을 갖습니다. 작업을 마감 시간 안에 완료했을 경우 1점, 그렇지 않으면 0점을 얻습니다. 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하세요.

입력:

n = 3
duration = [3, 2, 1]
deadline = [5, 2, 3]

출력:

해결:

마감 시간 기준 정렬: 각 작업을 마감 시간 (deadline)에 따라 오름차순으로 정렬합니다.
스케줄 구성: 정렬된 순서대로 작업을 스케줄에 추가합니다. 각 작업을 추가할 때, 현재 시점에서 작업 시간을 더하여 완료 시간을 계산하고, 마감 시간을 초과하는지 확인합니다.
점수 계산: 마감 시간 내에 완료된 작업의 개수를 세어 최대 점수를 계산합니다.

def max_score_job_scheduling(duration, deadline):
    """
    최대 점수 작업 스케줄링

    Args:
        duration: 각 작업의 작업 시간 리스트
        deadline: 각 작업의 마감 시간 리스트

    Returns:
        최대 점수
    """
    jobs = sorted(zip(duration, deadline), key=lambda x: x[1])  # (작업시간, 마감시간) 튜플 정렬

    current_time = 0
    score = 0
    for dur, dead in jobs:
        if current_time + dur <= dead:
            current_time += dur
            score += 1

    return score

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

그리디 알고리즘을 사용하여 작업 스케줄링 문제를 해결할 때는 몇 가지 주의해야 할 점이 있습니다.

최적해 보장 여부 확인: 그리디 알고리즘이 항상 최적해를 보장하는 것은 아닙니다. 문제의 특성을 정확히 파악하고, 그리디 선택이 최적해로 이어진다는 것을 증명하거나, 최적해에 근사하는 해를 찾는다는 것을 인지해야 합니다.
선택 기준의 적절성: 선택 기준을 잘못 설정하면, 최적해에서 멀어질 수 있습니다. 다양한 선택 기준을 시도해보고, 문제의 특성에 가장 적합한 기준을 선택해야 합니다. 테스트 케이스를 통해 알고리즘의 정확성을 검증하는 것이 중요합니다.
시간 복잡도와 공간 복잡도 고려: 그리디 알고리즘은 일반적으로 계산 복잡도가 낮지만, 문제의 규모가 커지면 시간 복잡도와 공간 복잡도를 고려해야 합니다. 효율적인 자료 구조를 사용하여 성능을 개선할 수 있습니다. 예를 들어, 작업을 정렬하는 과정에서 힙(heap) 자료구조를 사용하면 시간 복잡도를 개선할 수 있습니다.
예외 처리: 입력 데이터의 예외 상황 (예: 작업 시간, 마감 시간, 가중치 등이 음수인 경우)에 대한 처리를 고려해야 합니다.

6. 결론

작업 스케줄링은 다양한 분야에서 중요하게 다루어지는 문제이며, 그리디 알고리즘은 이러한 문제의 해결에 효과적으로 활용될 수 있습니다. 그리디 알고리즘의 장점은 빠른 계산 속도와 구현의 용이성에 있으며, 최적해에 근사하는 해를 찾는 데 유용합니다. 하지만, 그리디 알고리즘의 단점은 항상 최적해를 보장하지 않는다는 점입니다. 따라서 문제의 특성을 정확히 파악하고, 적절한 선택 기준을 설정하는 것이 중요합니다. 본 문서에서 제시된 내용과 예시들을 통해 작업 스케줄링 문제와 그리디 알고리즘에 대한 이해를 높이고, 실전 문제 해결 능력을 향상시킬 수 있기를 바랍니다. 다양한 문제 유형에 대한 경험을 쌓고, 그리디 알고리즘 외에도 다른 해결 방안들을 함께 학습한다면 더욱 효과적인 문제 해결 능력을 갖출 수 있을 것입니다.