G마켓 기술블로그

위상정렬 위상정렬 은 부분 순서를 갖는 집합을 정렬하는 방법입니다. 우리에게 익숙한 순서가 부여되는 집합인 전순서 집합에는 자연수, 실수 등이 있습니다. 이들은 임의의 원소를 두 개 꺼내면 둘 사이의 순서를 언제나 결정할 수 있는 게 특징입니다. 이와 다르게 모든 임의의 두 원소 사이에 순서를 결정하지 못하는 집합도 있습니다. 하지만 뭔가 집합에 포함된 순서가 있으면서도 말이죠. 알쏭달쏭 하지만 그런 문제는 일상에 많습니다. 흔히 드는 예시는 수강신청입니다. 수강하려는 과목들 사이에는 딱히 순서가 없지만, 어떤 과목에는 선수과목이 있곤 합니다. 이런 경우 부분적으로 발생하는 순서를 고려해서 수강 계획을 짜야하죠. 이처럼 작업관리에서는 흔하게 부분 순서를 갖는 문제를 쉽게 마주합니다. 이를 정렬할 수 있는..