Course Schedule
numCourses개의 강의가 있으며, 0부터 numCourses-1까지 번호가 매겨져 있습니다. prerequisites의 각 쌍 [a, b]는 강의 a를 시작하기 전에 강의 b를 끝내야 한다는 뜻입니다. 모든 강의를 끝낼 수 있는 순서가 있으면 true를 반환하고, 없으면 false를 반환하세요.
함수
- numCoursesinteger
- 과목 수
- prerequisitesinteger-2d-array
- 각 쌍 [a, b]는 과목 b가 과목 a보다 먼저 온다는 뜻입니다
- 반환값boolean
- 모든 과정을 완료할 수 있으면 true, 그렇지 않으면 false
제약 조건
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- 각 쌍
[a, b]에 대해0 ≤ a, b < numCourses입니다. - 어떤 쌍도 두 번 나타나지 않습니다.
- 한 쌍은 같은 과목을 두 번 지정할 수 있습니다.
[a, a]해당 과목은 자기 자신을 선수 과목으로 필요로 하므로 수강할 수 없습니다.
예제
- 입력
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- 출력
- true
- 설명
- 과목 0에는 선수 과목이 없으므로 가장 먼저 수강합니다. 그러면 과목 1을 수강할 수 있고, 이어서 2와 3도 수강할 수 있으므로 0, 1, 2, 3 순서가 가능합니다.
- 입력
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- 출력
- false
- 설명
- 과목 0은 2를 기다리고, 2는 1을 기다리며, 1은 0을 기다립니다. 세 과목은 루프에서 서로를 기다리므로 어느 과목도 먼저 시작할 수 없습니다.
후속 질문
각 과목의 선수 과목을 이전 학기에 이수했다면 한 학기에 몇 과목이든 들을 수 있습니다. 모든 과목을 이수하는 데 필요한 최소 학기 수는 몇 학기일까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
각 과목을 점으로, 각 쌍
[a, b]를b에서a로 향하는 화살표로 그려 보세요. 그 그림에서 어떤 모양이 있으면 과정을 모두 마칠 수 없을까요?화살표의 순환입니다. 순환에 속한 모든 과목은 같은 순환에 속한 다른 과목을 기다리므로, 그중 어느 것도 먼저 시작할 수 없습니다. 그래프에 사이클이 있는지가 관건입니다.
각 과목이 아직 몇 개의 선수 과목을 기다리고 있는지 세세요. 선수 과목 수가 0인 과목들로 큐를 시작하고, 과목 하나를 처리할 때마다 그 과목을 기다리는 모든 과목의 수를 줄이세요.
numCourses개보다 적은 과목만 큐에 들어간다면 사이클이 있습니다.
풀이
각 쌍 [a, b]마다 화살표 b → a를 그리세요. 이 그래프의 노드 수가 V = numCourses이고 화살표 수가 E = prerequisites.length일 때, 그래프에 사이클이 없으면 모든 과정을 이수할 수 있습니다. Kahn 알고리즘은 학생이 계획을 세우는 방식으로 이를 확인합니다. 선수 과목을 모두 마친 과정을 계속 수강하고, 모든 과정을 수강할 수 있는지 확인합니다.
모든 무료 강의를 라운드마다 수강하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
각 라운드에서 선수 과목을 모두 이수한 미이수 과목을 모두 이수합니다. 한 라운드에서 아무 과목도 이수하지 못하면 중단하고, 모든 과목을 이수했으면 true를 반환합니다. 한 라운드에서 아무 과목도 이수하지 못하는 경우는 남은 모든 과목이 다른 미이수 과목을 기다리는 경우뿐이며, 이는 순환입니다.
각 라운드마다 모든 쌍과 모든 과목을 다시 확인하지만, 한 과목만 이수할 수도 있습니다. 100,000개 중 5,001개 과목으로 이루어진 연쇄가 있으면 5,000회가 넘는 라운드가 필요합니다. 약 5 × 10^8번 확인해야 합니다.
알고리즘
- 모든 과목을 수강하지 않은 것으로 표시합니다.
- 어떤 쌍이 아직 수강하지 않은 선수 과목을 지정하는 경우 해당 과목을 수강 불가로 표시합니다.
- 수강하지 않았고 수강 불가도 아닌 모든 과목을 수강합니다.
- 이번 라운드에서 수강한 과목이 없다면 중단하고, 그렇지 않으면 2단계로 돌아갑니다.
- 모든 과목을 수강했다면 true를 반환합니다.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCourses세 가지 상태를 사용하는 깊이 우선 탐색
핵심 아이디어
깊이 우선 탐색은 따라가는 경로를 추적하여 순환을 찾습니다. 각 과목에 미방문, 경로상, 완료의 세 가지 상태 중 하나를 부여합니다. 과목에서 해당 과목을 기다리는 과목들로 이어지는 화살표를 따라갑니다. 과목에 진입하면 경로상으로 표시하고, 모든 화살표를 탐색하면 완료로 표시합니다.
경로상의 과목으로 향하는 화살표는 순환을 형성합니다. false를 반환합니다. 완료된 과목으로 향하는 화살표는 안전합니다. 그 과목에서 도달할 수 있는 모든 과목을 확인했고 순환이 없기 때문입니다. 따라서 어떤 과목에 두 번 도달하는 것만으로는 순환이 아닙니다. 각 과목은 한 번씩 진입하고 각 화살표는 한 번씩 따라갑니다. O(V + E).
알고리즘
- 각 강의에 대해 자신을 기다리는 강의 목록을 만듭니다.
- 방문하지 않은 각 강의를 경로에 표시하고 스택에 넣습니다.
- 스택의 맨 위를 확인합니다. 남은 화살표가 없으면 완료로 표시하고 스택에서 꺼냅니다. 그렇지 않으면 다음 화살표를 따라갑니다.
- 화살표가 경로에 있는 강의로 이어지면 false를 반환합니다. 방문하지 않은 강의로 이어지면 해당 강의를 경로에 표시하고 스택에 넣습니다.
- 모든 강의가 완료되면 true를 반환합니다.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return True칸 알고리즘
핵심 아이디어
과목은 마지막 선수 과목을 이수하는 순간 수강 가능해집니다. 따라서 각 과목의 진입 차수, 즉 아직 기다리고 있는 선수 과목의 수를 기록하고, 그 수가 0인 모든 과목을 큐에 넣고 시작합니다. 한 과목을 이수하면 그 과목을 기다리는 각 과목의 수를 줄이고, 수가 0이 되면 해당 과목을 큐에 넣습니다. 첫 번째 예시에서는 수가 0, 1, 1, 1로 시작합니다. 0을 이수하면 1을 수강할 수 있게 되고, 1을 이수하면 2와 3을 수강할 수 있게 됩니다. 각 과목은 큐에 한 번 들어가고 각 쌍은 수를 한 번 줄이므로, 시간 복잡도는 O(V + E)입니다.
과목 a를 아직 이수하지 않은 상태에서 큐가 비면, a의 수는 0보다 큽니다. 즉, a의 선수 과목 중 하나도 아직 이수하지 않은 상태이며, 이런 식으로 계속 따라가다 보면 반드시 어떤 과목을 다시 방문하게 됩니다. 이것이 사이클입니다. 반대로 사이클에 속한 각 과목은 그 사이클의 다른 과목을 기다리므로, 어느 과목도 먼저 이수할 수 없습니다. 과목이 큐에서 나오는 순서는 유효한 수강 계획입니다.
알고리즘
- 각 쌍 [a, b]에 대해, b를 기다리는 과목 목록에 a를 추가하고 a의 진입 차수에 1을 더합니다.
- 진입 차수가 0인 모든 과목을 큐에 넣습니다.
- 큐에서 과목 하나를 꺼내 세고, 그 과목을 기다리는 모든 과목의 진입 차수를 낮춥니다. 진입 차수가 0이 된 각 과목을 큐에 넣습니다.
- 큐가 비면 개수가
numCourses와 같은지 반환합니다.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
함정과 경계 사례
- 방향을 혼동하는 것.
[a, b]는 b가 먼저 온다는 뜻입니다. 화살표는 b에서 a로 향하고, a의 진입 차수는 증가합니다. - 어떤 쌍에도 등장하지 않는 과목을 잊는 것.
numCourses = 5이고 쌍이[4, 3]하나뿐이라면 과목 0, 1, 2도 큐에서 시작해야 합니다. - 깊이 우선 탐색에서 세 가지 상태 대신 두 가지 상태만 사용하는 것. 0 → 1, 0 → 2, 1 → 3, 2 → 3으로 이어지는 다이아몬드 구조에서 과목 3에 두 번 도달하게 되며, "방문함"만 추적하면 순환처럼 보입니다.
- 과목 5,000개로 된 사슬에서 재귀 호출을 하는 것: 호출 깊이가 5,000이 되어 Python의 기본 한도인 1,000을 넘습니다.
numCourses개의 과목을 이수했는지 확인하지 않고 큐가 비었을 때 true를 반환하는 것. 두 번째 예제에서는 true를 반환하게 됩니다.
자주 묻는 질문3
Course Schedule 문제의 시간 복잡도는 얼마인가요?
O(V + E)이며, 여기서 V는 강의 수이고 E는 쌍의 수입니다. Kahn의 알고리즘이나 깊이 우선 탐색을 사용합니다. 각 쌍은 한 번씩 읽고, 각 강의는 한 번씩 처리합니다. 목록과 개수를 저장하는 데 O(V + E) 공간이 필요합니다.
강의 일정에는 BFS를 사용해야 할까요, DFS를 사용해야 할까요?
둘 다 O(V + E) 시간에 실행됩니다. 너비 우선 방식인 칸 알고리즘은 재귀 깊이를 걱정할 필요가 없고 유효한 과목 순서를 제공합니다. 사이클도 보고해야 한다면 세 가지 상태를 사용하는 깊이 우선 탐색이 자연스러운 선택입니다. 탐색 스택에 있는 과목들이 사이클을 이루기 때문입니다.
위상 정렬이란 무엇인가요?
모든 화살표가 앞쪽을 가리키는 방향 그래프 노드의 순서입니다. 여기서는 모든 선수 과목이 해당 과목보다 먼저 오는 순서입니다. 그래프에 사이클이 없을 때에만 존재하며, Kahn 알고리즘이 과목을 선택하는 순서가 그중 하나입니다. Course Schedule은 이러한 순서가 존재하는지 묻습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def canFinish(numCourses, prerequisites):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자들
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
예상 출력
true