topological sorting이란 무엇인가요?

Question

IT Interview Practice · Accepted Answer

**Topological sort(위상 정렬)**는 **DAG**(방향 비순환 그래프)의 정점을 선형으로 정렬하여 모든 간선 u->v에서 u가 v보다 **앞에** 오도록 합니다. "이 작업들을 그 의존성을 고려할 때 어떤 순서로 할 수 있는가?"에 답합니다.

## 개념

흔한 두 가지 접근: **Kahn 알고리즘**(in-degree가 0인 노드를 반복적으로 제거) 또는 **DFS**(역 후위 순서). 유효한 정렬은 **사이클이 없을 때만** 존재합니다.

## 예시 (Kahn 알고리즘)

```python
from collections import deque

def topo_sort(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1                 # 들어오는 간선 수 세기
    queue = deque([u for u in indeg if indeg[u] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1                 # 간선 "제거"
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None  # None -> 사이클

topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
```

## 복잡도

- **시간:** O(V + E). **공간:** O(V).

## 언제 사용하나 / 함정

**빌드 시스템**, 작업 스케줄링, 강의 선수 과목, 의존성 해결에 사용하세요. 결과가 V보다 짧으면 그래프에 **사이클**이 있습니다(유효한 순서 없음). 정렬은 일반적으로 **유일하지 않습니다**.

## 왜 중요한가

의존성 정렬은 어디에나 있습니다 — 컴파일러, 패키지 관리자, 스프레드시트 재계산, CI 파이프라인.

Topological sort는 방향 그래프의 사이클 탐지 역할도 겸합니다.

문제를 "제약 하의 순서 정하기"로 인식하고 topo sort로 손을 뻗는 것은 강력한 시니어 신호입니다.

개념

예시 (Kahn 알고리즘)

복잡도

언제 사용하나 / 함정

왜 중요한가

관련 질문