위상정렬

이 문제는 백준 키순서에 내가 적어놓은 예시와 거의 유사한 문제였다. 문제집 커리큘럼에 따라 한 문제를 풀기 위해서는 선행되어야 하는 문제(진입 차수)가 있고, 이 문제는 그 순서대로 문제를 풀 때 어떤 순서대로 풀어야 할지를 묻는 문제이다. 여기서 하나의 추가조건이 있는데 가능하다면 쉬운 문제 (인덱스가 작은 문제)를 먼저 풀어야 한다. 나는 이 부분에서 조금 헷갈렸는데 이 문제가 원하는 것은 2번 문제(선행 문제가 1인 문제)와 3번 문제(선행 문제가 없는 문제)가 있다면 1-2-3 순서로 문제를 풀어야 한다. 즉, 선행 문제가 있다 하더라도 문제의 난이도는 인덱스가 결정한다. 위상 정렬과 문제만 이해했다면, 쉽게 풀 수 있을 것이다. 우리에게는 자동으로 인덱스를 정렬해주는 힙이라는 무기가 있기 때문..

줄 세우기 문제이다. 백준의 키순서와 비슷하다는 느낌이었지만 백준의 키순서 문제는 자신의 순서를 정확히 알 수 있는 사람의 수를 묻는 문제였고, 순서를 정렬(정확하지 않는 사람은 임의로)한다는 점에서 차이가 있었다. 이 차이에 의하여 키순서문제는 플로이드 와샬이나 dfs를 통해 푸는 문제가 되었고, 이 문제는 위상 정렬을 통해 푸는 문제가 되었다. 위상 정렬은 진입 차수가 낮은 노드들 순으로 정렬할 때 활용하는 알고리즘이며 일상생활에서도 우리가 흔히 쓰고 있는 알고리즘이다. 대표적으로 대학교의 수강커리큘럼을 볼 때 우리가 무의식적으로 많이 사용하고 있는데 어떤 한 과목을 듣기 위해서 선수과목이 있고, 그 과목의 또 선수과목이 있다. 우리는 이를 보기 쉽게 하기 위해 선수과목의 수준이 낮은 것부터 정렬하여..