DSA Interview Prep · 강의

과목 일정 I과 II

과목 선수 조건을 방향 그래프로 모델링하고 위상 정렬을 사용해 모든 과목을 이수할 수 있는지와 그 순서를 결정합니다.

과목 일정 I과 II은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

문제 개요

과목 일정 I (LeetCode 207): n개의 과목과 prerequisites 쌍의 목록이 주어집니다. [a, b]는 'b를 a보다 먼저 수강해야 한다'는 뜻이며, 모든 과목을 이수할 수 있는지 판단해야 합니다. 과목 일정 II (LeetCode 210): 실제 과목 수강 순서를 반환하고, 불가능하면 빈 배열을 반환합니다. 두 문제 모두 선수 과목을 간선으로 표현한 방향 그래프의 위상 정렬 문제로 환원됩니다.

그래프 모델링

방향 그래프를 구성합니다. 각 선수 과목 쌍 [a, b]에 대해 b → a 간선을 추가합니다. 'b가 a보다 먼저 와야 한다'는 뜻이므로 b에서 a로 이어집니다. 각 과목의 진입 차수를 계산합니다. 진입 차수가 0인 과목은 선수 과목이 없으므로 즉시 수강할 수 있습니다. 이 그래프에 사이클이 존재하지 않을 때 그리고 오직 그때만 문제를 해결할 수 있습니다. 즉, 순환 의존성이 없어야 합니다.

from collections import defaultdict

def build_graph(n, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * n
    for a, b in prerequisites:  # b must come before a
        graph[b].append(a)
        in_degree[a] += 1
    return graph, in_degree

graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind)   # [0, 1, 1, 2]
print('Graph edges:', dict(graph))

과목 일정 I: 칸 알고리즘 풀이

칸 알고리즘을 사용합니다. 처리한 과목 수가 n과 같으면 모든 과목을 이수할 수 있습니다. 그렇지 않으면 순환 의존성 때문에 완료할 수 없습니다.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    
    while queue:
        course = queue.popleft()
        count += 1
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))        # True
print(canFinish(2, [[1,0],[0,1]])) # False

과목 일정 II: 순서 반환

과목 일정 I와 같은 방식으로 처리하되, 과목을 처리하는 순서를 모읍니다. 모든 과목이 포함되어 있으면 그 순서를 반환하고, 그렇지 않으면 빈 목록을 반환합니다.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    
    while queue:
        course = queue.popleft()
        order.append(course)
        for nxt in graph[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

DFS를 사용하는 과목 일정

DFS를 사용하여 사이클을 탐지하는 다른 방법도 있습니다. 과목에는 방문하지 않음(0), 처리 중(1), 완료(2)의 세 가지 상태가 있습니다. DFS 중 처리 중인 과목에 다시 도달하면 사이클이 존재합니다. 이 방법은 칸 알고리즘과 기능적으로 동일하지만 재귀 DFS를 사용합니다.

from collections import defaultdict

def canFinish_dfs(numCourses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)
    
    # 0=unvisited, 1=in-progress, 2=done
    state = [0] * numCourses
    
    def has_cycle(course):
        if state[course] == 1: return True  # back edge
        if state[course] == 2: return False # already cleared
        state[course] = 1
        for nxt in graph[course]:
            if has_cycle(nxt):
                return True
        state[course] = 2
        return False
    
    return not any(has_cycle(i) for i in range(numCourses))

print(canFinish_dfs(2, [[1,0]]))        # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # False

간선 방향이 중요한 이유

흔히 하는 실수는 간선 방향을 반대로 설정하는 것입니다. 선수 과목이 [a, b]이고 'b가 a보다 먼저'라는 뜻이라면 a → b가 아니라 b → a 간선을 추가해야 합니다. 간선 방향은 의존성의 흐름을 나타내야 합니다. 화살표는 먼저 처리해야 하는 항목에서 그 항목에 의존하는 항목을 향해야 합니다. 방향을 잘못 설정하면 사이클 탐지와 순서가 반대로 되어, 여러 의존성이 있는 문제에서 잘못된 결과를 얻게 됩니다.

과목 일정 III: 탐욕적 변형

과목 일정 III (LeetCode 630)는 다른 문제입니다. 과목마다 소요 기간과 마감일이 주어지고, 수강하는 과목 수를 최대화해야 합니다. 이 문제는 최대 힙을 사용하는 탐욕적 방법으로 해결합니다. 항상 마감일이 가장 늦은 과목을 먼저 선택하고, 과목을 추가했을 때 마감일을 넘기면 지금까지 선택한 과목 중 가장 긴 과목으로 교체합니다(그 과목이 더 긴 경우). 이는 위상 정렬 문제가 아니라 탐욕적 문제이므로, 문제 설명을 주의 깊게 읽는 것이 중요합니다.

고립된 노드 처리

선수 과목도 없고 해당 과목에 의존하는 과목도 없는 과목은 고립된 노드입니다. 진입 차수가 0이고 나가는 간선도 없습니다. 칸 알고리즘은 이러한 노드를 올바르게 처리합니다. 즉시 큐에 넣고 처리합니다. 선수 과목 목록에 나타나지 않는 노드까지 포함하여 ALL 노드의 진입 차수를 0으로 초기화해야 합니다. 그렇지 않으면 해당 노드가 누락됩니다.

# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict

def findOrder_isolated(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses  # initialise ALL nodes
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        c = queue.popleft(); order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    return order if len(order) == numCourses else []

print(findOrder_isolated(4, [[1,0]]))  # [0,1,2,3] or [2,3,0,1] etc.

병렬 과목 이수 시간

병렬 과목 II: 한 학기에 최대 k개의 과목만 수강할 수 있고 선수 과목 조건을 지켜야 할 때, 모든 과목을 이수하는 데 필요한 최소 학기 수를 구하는 문제입니다. 이를 위해서는 단계별로 처리하는 칸 알고리즘과 k개 선택 제약을 위한 비트마스크 DP가 필요합니다. 위상 정렬과 비트마스크 DP를 결합한 훨씬 더 어려운 문제입니다.

면접 의사소통 전략

면접에서 과목 일정 유형의 문제를 만났을 때는 다음과 같이 하십시오. (1) 즉시 식별하여 위상 정렬 및 사이클 탐지 문제로 파악합니다. (2) 간선이 어느 방향을 향하는지 명확히 하여 그래프를 모델링합니다. (3) 간단한 풀이를 원하면 칸 알고리즘(BFS)을, 익숙한 방법을 원하면 DFS를 선택합니다. (4) 사이클이 있는 경우를 명시적으로 처리합니다. (5) 시간 복잡도 O(V+E)를 언급합니다. 이러한 구조적인 접근은 체계적인 문제 해결 능력을 보여 줍니다.

종합 테스트

두 풀이를 다양한 입력에 대해 테스트하여 올바르게 동작하는지 확인합니다. 칸 알고리즘은 여러 유효한 순서를 자연스럽게 처리하므로, 과목 일정 II의 답으로는 어떤 유효한 위상 순서든 허용됩니다.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        c = queue.popleft(); order.append(c)
        for nxt in graph[c]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    return order if len(order) == numCourses else []

print(findOrder(1, []))                    # [0]
print(findOrder(2, [[0,1]]))              # [1, 0]
print(findOrder(3, [[1,0],[2,1]]))        # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]]))        # [] cycle

빠른 확인

이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 테스트하십시오.

단원 복습

이 단원에서는 다음을 배웠습니다. 과목 일정 I과 II는 모두 선수 과목 [a, b]에 대해 b → a 간선을 사용하는 위상 정렬을 적용합니다. 과목 일정 I은 순서에 포함된 항목 수가 n인지 확인하기만 하지만, 과목 일정 II는 순서 자체를 반환합니다. 또한 세 가지 상태를 사용하는 DFS 기반 사이클 탐지는 칸 알고리즘의 BFS 방식에 대한 유효한 대안입니다. 다음에는 강한 연결 요소를 찾는 코사라주 알고리즘을 살펴봅니다.

자주 묻는 질문

“과목 일정 I과 II” 강의는 무료인가요?

네 — “과목 일정 I과 II” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“과목 일정 I과 II”에서 뭘 배우나요?

과목 선수 조건을 방향 그래프로 모델링하고 위상 정렬을 사용해 모든 과목을 이수할 수 있는지와 그 순서를 결정합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“과목 일정 I과 II” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← DSA Interview Prep(으)로 돌아가기