👀 finalfrontier

👆 Sound of Sorting 정렬 알고리즘의 분류 Stable Sorting : 중복된 원소의 순서가 정렬된 후에도 유지됨이 보장된다. Unstable Sorting : 중복된 원소의 순서가 정렬된 후에 유지됨이 보장되지 않는다. K1, .., K2, .. 순서인 배열에서 정렬 후 K1, K2 임이 보장되면 stable, K2, K1일 수 있으면 unstable in-place: 내부 정렬, 정렬을 위해 외부 배열이 필요하지 않다. not in-place: 외부 정렬, 정렬을 위해 외부 배열이 필요하다. 🔥 핵심은 **교환/선택/삽입** 이다. 대부분의 정렬 알고리즘은 이 세 가지 개념을 응용한다. 1. O(N^2) 알고리즘 1. 교환 정렬 Exchange Sort for i in range(0, ..

위상 정렬 위상 정렬이란? 위상 정렬 Topological Sorting 이란 방향이 있는 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 즉 한 정점에 도달하기 전 먼저 거쳐야 하는 정점들의 순서가 있는 경우 사용하는 알고리즘이다. 만약 특정 수강과목에 선수과목이 있다면 그 선수과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 대 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 방향이 있는 (유향의) 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가..