위상정렬 알고리즘
위상정렬 알고리즘이란 우선순위가 정해져있는 작업을 처리할 때, 해당 작업의 순서를 결정해주기 위한 알고리즘이다. 대학의 수강신청을 예를 들어보자. 과목 1, 2, 3, 4, 5가 있다. 3번 과목을 듣기 위해선 4번 과목을, 5번 과목을 듣기 위해선 1번 과목을 사전에 들을 필요가 있다.(선수과목) 이 경우 다음 과 같이 표현할 수 있다. 4 -> 3 1 -> 5 전체 순서를 구했을 때, 4번이 3번보다 앞에 있어야 하고, 1번이 5번보다 앞에 있어야 한다. 조건이 적을 경우 간단히 생각하는 것 만으로도 순서를 구할 수 있다. 위의 예시의 경우 1번과 4번을 앞에 적어주고 2, 3, 5번을 뒤에 적어주는 식으로(ex: 1 4 2 3 5) 답을 출력할 수 있다. 그러나 조건이 많아진다면 위와 같은 단순한 ..
프로그래밍/코테 준비
2024. 3. 3. 18:12