티스토리 뷰

카테고리 없음

위상 정렬 완벽 가이드: 선후 관계가 있는 작업 스케줄링

머니지니87 2026. 4. 9. 23:29

목차


    대학교 전공 과목을 이수할 때, '자료구조'를 듣기 위해서는 반드시 '프로그래밍 기초'를 먼저 들어야 한다는 조건이 있습니다. 이처럼 작업들 사이에 명확한 선후 관계가 존재할 때, 이를 논리적인 순서로 나열하는 기법이 바로 위상 정렬(Topological Sort)입니다. 위상 정렬은 단순히 데이터를 정렬하는 것을 넘어, 시스템의 의존성 관리나 작업 스케줄링의 근간을 이룹니다. 본 포스팅에서는 위상 정렬의 성립 조건인 DAG의 개념과 Kahn 알고리즘을 이용한 구현 원리를 2,500자 이상의 상세한 설명으로 분석해 보겠습니다.

    1. 위상 정렬의 정의와 필수 전제 조건: DAG

    위상 정렬은 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 말합니다. 하지만 모든 그래프에서 위상 정렬이 가능한 것은 아닙니다. 가장 중요한 전제 조건은 해당 그래프가 DAG(Directed Acyclic Graph), 즉 '사이클이 없는 방향 그래프'여야 한다는 점입니다. 만약 A를 하기 위해 B가 필요하고, B를 하기 위해 A가 필요한 사이클이 존재한다면, 논리적으로 어떤 작업도 시작할 수 없는 교착 상태에 빠지게 됩니다.

    1-1. 진입 차수(In-degree)의 논리적 의미

    위상 정렬의 핵심 지표는 진입 차수(In-degree)입니다. 특정 노드로 들어오는 간선의 개수를 의미하며, 이는 해당 작업을 수행하기 위해 먼저 해결되어야 할 '선행 작업의 개수'로 해석할 수 있습니다. 진입 차수가 0인 노드는 즉시 실행 가능한 상태임을 의미하며, 위상 정렬 알고리즘은 항상 이 지점들로부터 시작됩니다.

    2. Kahn 알고리즘: 큐(Queue)를 이용한 효율적 정렬

    위상 정렬을 구현하는 가장 대표적인 방법은 Kahn 알고리즘입니다. 이 방식은 너비 우선 탐색(BFS)의 원리를 차용하여, 실행 가능한 작업(진입 차수 0)들을 순차적으로 큐에 담아 처리합니다.

    2-1. 알고리즘의 단계별 동작 프로세스

    1. 모든 노드의 진입 차수를 계산합니다.
    2. 진입 차수가 0인 모든 노드를 큐에 삽입합니다.
    3. 큐가 빌 때까지 다음 과정을 반복합니다.
      • 큐에서 노드를 꺼내 결과 리스트에 추가합니다.
      • 해당 노드에서 나가는 모든 간선을 제거합니다. 즉, 연결된 인접 노드들의 진입 차수를 1씩 감소시킵니다.
      • 새롭게 진입 차수가 0이 된 노드를 큐에 삽입합니다.

    이 과정에서 모든 노드를 방문하기 전에 큐가 비어버린다면, 해당 그래프에는 사이클이 존재한다는 증거가 됩니다. 이러한 자가 진단 기능을 통해 위상 정렬은 시스템의 무결성을 검증하는 도구로도 쓰입니다.

    3. 위상 정렬의 실무 활용 사례

    위상 정렬은 우리 눈에 보이지 않는 수많은 시스템 소프트웨어 내부에서 작동하고 있습니다.

    • 컴파일러 빌드 시스템: 수천 개의 소스 코드 파일 사이의 의존 관계를 분석하여 컴파일 순서를 결정할 때(Makefile, Gradle 등).
    • 데이터 파이프라인(Airflow): 빅데이터 처리 과정에서 각 연산 단계별 실행 순서 제어.
    • 수강 신청 시스템: 선수 과목 체계를 분석하여 적절한 커리큘럼 순서 제시.
    • 패키지 매니저: 라이브러리 간의 복잡한 설치 의존성을 해결할 때(npm, pip 등).

    4. 시간 복잡도와 성능 최적화

    위상 정렬의 시간 복잡도는 모든 노드(V)와 간선(E)을 한 번씩만 확인하기 때문에 $O(V + E)$로 매우 효율적입니다. 대규모 데이터셋에서도 선형 시간 내에 정렬이 완료되므로, 복잡한 의존성 그래프를 가진 대규모 엔터프라이즈 시스템에서도 성능 저하 없이 안정적으로 동작합니다.

    
# 위상 정렬 Kahn 알고리즘 구현 (Python)
from collections import deque

def topological_sort(v, adj, indegree):
    result = []
    q = deque()
    
    # 1. 진입 차수가 0인 노드 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)
            
    while q:
        now = q.popleft()
        result.append(now)
        # 2. 연결된 간선 제거 및 진입 차수 갱신
        for i in adj[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
                
    return result if len(result) == v else "Cycle Detected"
    [위상 정렬 핵심 요약]
    1. 대상: 사이클이 없는 방향 그래프(DAG)에서만 유효한 정렬이 가능합니다.
    2. 지표: 진입 차수가 0인 노드부터 순차적으로 처리하여 의존성을 해소합니다.
    3. 활용: 빌드 시스템, 소프트웨어 패키지 관리, 작업 스케줄링 등 의존성 정렬의 표준입니다.