남남서의 블로그

190616. 제 블로그 조회수의 상당수를 차지하는 글입니다. 특히 대학교 시험 기간인 6월에 많이들 찾아주시더라구요. 그런 것 치고는 글이 너무 오래 되어서, 글을 완전히 다시 쓰고 연습문제를 몇 개 추가했습니다. 위상정렬은 방향 그래프(directed graph) 문제에서 쓰입니다. 또는 직접 그래프가 주어지지 않는 경우에도, 문제에 나타난 요소들을 점으로 나타내고 그 사이에 화살표를 그렸을 때 방향 그래프가 나타나는데, 문제를 푸는 과정에서 위상 정렬이 꼭 필요한 경우도 있습니다. 먼저 위상 정렬을 대강의 느낌으로 설명해 보려고 합니다. a → b를 "a가 충족되어야만 b를 할 수 있다"는 뜻으로 생각해봅니다. 예를들어 a가 세탁기를 돌리기, b가 건조기 사용하기라면, 세탁기를 돌리는 일을 마쳐야 ..