prefer2 Log

위상 정렬? 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 이론적으로는 비순환 방향 그래프(DAG, Direct Acyclic Graph)에서 그래프의 방향성을 거르지 않고 정점들을 나열하는 알고리즘이다. 예를 들어 A작업이 끝난 후 B작업을 실행할 수 있고, C작업이 끝난 후 B작업을 실행할 수 있다고 할때 작업의 순서는 ACB 또는 CAB가 될 수 있다. 이렇게 정해진 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘을 위상 정렬이라고 한다. 일반적으로 위상 정렬의 결과는 유일하지 않다. 동작 과정 배열에 각 노드들의 진입 차수를 저장한다. queue에는 진입차수가 0인 모든 노드들이 삽입된다. queue의 첫번째 값을 꺼낸다. 이 노드에 연결된 모든 ..

문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다. 1 4 3 6 2 5 4 2 3 첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다. 한 가수를 여러 보조 PD가 담당할 수도 있다. 마지막으로, 세 번째 ..