정렬
[Sort] Topology Sort (위상 정렬)
그래프에서의 정렬 방법으로, 유향 그래프의 꼭짓점 변의 방향을 거스르지 않도록 나열 하는 것이다. 정의 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다. 설명 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리..
[Sort] Counting Sort (카운팅 정렬)
항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 정의 일반적으로 정렬 대상이 integer이고 최대값이 크지 않을때 사용한다. 정렬 대상을 인덱스로 하는 카운팅 배열을 생성하여, 정렬 대상의 갯수를 센다(카운팅) 카운팅 배열을 누적값으로 만들면 각 인덱스가 최대 누적값 번째에 있는 숫자가 된다. 제한 사항 정수나, 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다. 시간복잡도 O(n + k) : n은 리스트의 길이, k는 정수의 최대값 구현 def Co..