위상 정렬이란? 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 위상 정렬의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라고 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. 위상 정렬 이용하는 방법 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택을 하고 Queue에 모두 넣는다. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택 선택되어진 정점을 Queue에서 제거 선택된 정점에 속해있는..

퀵 정렬이란? 퀵 정렬은 배열 중 적당한 수 (Pivot)을 골라 그 기준으로 그 수보다 작은 원소와 큰 원소로 나누어서 분류하는 것. 퀵 정렬 아이디어 비어있는 배열 || 원소가 1개인 배열 ㅡ 정렬을 할 필요가 없음. 원소가 2개 라면? ㅡ 아주 쉽다. 그냥 두 개의 위치(swap)를 바꾸기만 하면 된다. 원소가 3개 이상이라면? 우선 원소가 3개라고 가정해보자 { 4, 3 , 1 } 여기서 우리가 4(Pivot)를 선택한다고 하자. 1 . 왼쪽 배열에 작은 원소를 나열해보자 { 3 , 1 } + Pivot + 오른 배열에 큰 원소를 나열해보자 { X } 이렇게 Pivot에 의해 큰 원소와 작은 원소로 나뉘는 것을 분할(Partitioning) 이라 한다. 2 . 이제 왼쪽 배열과 오른쪽 배열을 보자..