0. 위상 정렬(Topological Sort)위상 정렬은 유향 그래프의 정점들을 나열하는 것을 의미한다.순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘으로 위상 정렬의 결과는 여러 개일 수 있다.가장 잘 설명되는 예시로는 선수과목(prerequisite) 구조이다. 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 수강 순서를 찾아낼 수 있다.위상 정렬이 성립하기 위해서는 그래프의 순환이 존재하지 않는 비순환 유향 그래프(directed acyclic pragh)여야 한다. 위상 정렬은 아래 2가지에 대한 판단이 가능하다.현재 그래프는 위상 정렬이 가능한지 → 사이클이 존재하지 않는지위상 ..

0. 병합 정렬병합 정렬은 O(NlogN)의 시간복잡도를 가진 정렬 알고리즘이다.가장 일반적인 O(N^2)인 삽입, 선택, 버블 정렬보다 빠르며,많이 쓰이는 퀵 소트보다 높은 안정성을 보여준다.퀵 소트는 평균적으로 O(NlogN)이지만 최악의 경우 O(N^2)이기 때문이다.(이 이유때문에 알고리즘 문제에선 절대 퀵소트를 써선 안된다...)자세한 건, 퀵 소트를 찾아보면 이해가 될 것이다.1. 알고리즘n의 길이를 가진 배열을 절반(m) 크기의 배열로 쪼갠다.쪼개진 배열의 길이가 2가 될 때까지 1번을 반복한다.쪼개진 두 배열을 [그림 1]과 같이 정렬한다.m 길이의 정렬된 배열을 통해 2 * m 길이의 배열도 정렬한다.2 * m이 n이 될때까지 4번을 반복한다. 2. 코드3. 참고https://www.yo..