선행 조건을 지키면서 모든 작업의 실행 순서를 만드는 알고리즘
작업 A가 끝나야 B를 시작할 수 있는 의존 관계에서 가능한 전체 순서를 찾습니다. 빌드, 수강 과목, 데이터 파이프라인처럼 방향성과 선후 관계가 핵심인 문제에 맞습니다.
코드를 생각하지 말고, 아래 상황이 어떤 순서로 움직이는지만 따라가 보세요.
물을 끓이기 전에 면을 익힐 수 없고, 면을 익힌 다음에야 그릇에 담을 수 있습니다.
양말을 신은 뒤 신발을 신고, 셔츠를 입은 뒤 재킷을 입어야 합니다. 서로 관계없는 일은 순서가 바뀌어도 됩니다.
코딩 테스트의 장난감 예제를 넘어, 실제 시스템에서 같은 원리가 어디에 숨어 있는지 연결해 보세요.
의존 라이브러리를 먼저 빌드한 뒤 애플리케이션을 빌드합니다.
입력 데이터가 준비된 작업부터 실행합니다.
의존 패키지를 올바른 순서로 설치하고 순환 의존을 탐지합니다.
선행 스키마 변경을 먼저 적용한 뒤 의존하는 변경을 실행합니다.
테스트를 통과한 뒤 빌드하고, 빌드가 끝난 뒤 배포하도록 순서를 정합니다.
방향 비순환 그래프(DAG)에서만 가능합니다. Kahn 알고리즘은 진입 차수가 0인 정점을 큐에 넣고, 꺼낼 때마다 나가는 간선을 제거합니다. 모든 정점을 처리하지 못했다면 사이클이 있습니다.
| 연산 | Python 표현 | 시간 |
|---|---|---|
| 진입 차수 계산 | indegree | O(V+E) |
| 0차수 큐 구성 | deque | O(V) |
| 간선 제거 | indegree[next] -= 1 | O(E) |
| 사이클 판별 | 결과 길이 < V | O(1) |
A=0, B=0, C=2, D=1C의 차수 2→1→0D의 차수 1→0가능한 순서 A, B, C, D설명을 닫고 먼저 풀어본 뒤, 막히는 지점에서 어떤 연산이 필요한지 다시 떠올려 보세요.
Easy 연습 1 / 7
Python으로 풀기Easy 연습 2 / 7
Python으로 풀기Easy 연습 3 / 7
Python으로 풀기Easy 연습 4 / 7
Python으로 풀기Easy 연습 5 / 7
Python으로 풀기Easy 연습 6 / 7
Python으로 풀기Easy 연습 7 / 7
Python으로 풀기Medium 연습 1 / 3
Python으로 풀기Medium 연습 2 / 3
Python으로 풀기Medium 연습 3 / 3
Python으로 풀기