Algorithm
-
9. 정렬 알고리즘 정리Algorithm 2019. 10. 16. 17:59
#정렬 알고리즘 Best Worst Average Stable In-place Selection Sort O(n*n) O(n*n) O(n*n) X O Bubble Sort O(n*n)/ O(n) O(n*n) O(n*n) O O Insertion Sort O(n) O(n*n) O(n*n) O O Quick Sort O(n log n) O(n*n) O(n log n) X X Merge Sort O(n log n) O(n log n) O(n log n) O X Heap Sort O(n log n) O(n log n) O(n log n) X O Merge Sort의 경우 병합할 때 O(n)의 스텍 메모리가 필요하다. // O(log n) Quick Sort의 경우 O(n)의 stack 메모리가 필요하다. 하지만..
-
7. 힙 정렬(Heap Sort)Algorithm 2019. 10. 16. 16:29
#힙이란? 힙은 다음 두가지 성질을 가지는 이진트리이다. 1. 구조적 성질: 완전이진트리 2. 힙의 성질: 최대힙 or 최소힙 *완전이진트리 -마지막 레벨을 제외하고 모든 레벨이 가득 차 있는 상태 -마지막 레벨에서 노드는 왼쪽부터 차례로 채워져야 한다. *Max Heap & Min Heap -최대힙: 모든 노드 x에 대하여, 그 x의 값은 자신의 자식 노드의 값보다 크거나 같아야 한다. -최소힙: 모든 노드 x에 대하여, 그 x의 값은 자신의 자식 노드의 값보다 작거나 같아야 한다. -최대힙에서 최댓값을 찾는 시간과 최소힙에서 최솟값을 찾는 시간은 O(1)로 상수 시간을 가진다. 그 값은 root에 있기 때문이다. 하지만 최대힙에서 최솟값을 찾거나 최소힙에서 최대값을 찾는 것은 노드를 탐색하는 과정이 ..
-
6. 분할과 정복_퀵정렬(Quick Sort)Algorithm 2019. 10. 4. 21:05
#퀵 정렬 알고리즘 1. 배열 a에서 pivot을 선택한다. 2. 배열 a를 다음과 같이 분할한다: pivot보다 같거나 작은 수는 pivot의 왼쪽으로, pivot보다 큰 수는 pivot의 오른쪽으로 이동하여 재 배열한다. 3. 분할된 두 리스트를 각각 재귀적으로 정렬한다. 즉, 같은 방법(단계1과 단계2)을 적용한다. 한번의 루프(재귀)를 돌고나면 다음과 같이 원소들이 나뉜다. (단계1과 2를 거친 배열의 모습) pivot보다 같거나 작음 pivot pivot보다 큼 여기서 pivot이란 기준 값으로 정렬하고자 하는 원소들 중 첫 인덱스, 중간 원소, 마지막 인 원소, 무작위 선택 등 하나를 정하면 된다. 무작위로 선택하는 방법이 가장 많이 사용된다. 하지만 여기서는 pivot이 첫 번째 원소인 경우..
-
5. 분할과 정복_병합정렬(Merge Sort)Algorithm 2019. 10. 4. 02:02
#분할과 정복을 이용한 정렬 -병합정렬 -퀵정렬 #분할과 정복 알고리즘 1. 큰 문제를 작은 문제들로 나눈다. 2. 단계1의 작은 문제들의 해를 재귀적으로 구한다. 3. 단계2에서 구한 작은 문제들의 해를 이용하여 원래 문제의 해를 구한다. #병합정렬 알고리즘 1. 주어진 크기가 n인 리스트를 크기가 n/2인 두 부분으로 나눈다. 2. 크기가 n/2인 두 부분을 재귀적으로 정렬한다. 3. 정렬된 두 부분을 하나로 병합한다. #구현 #include using namespace std; int* sorted; void mergesort(int a[], int first, int last); void merge(int a[], int first, int mid, int last); int main(){ int..
-
3. 버블 정렬(Bubble Sort)Algorithm 2019. 10. 4. 01:00
#버블 정렬 알고리즘 1. 매 단계마다 처음부터 마지막까지 차례대로 인접한 두 원소를 비교하여 뒤에 있는 원소가 앞의 원소보다 작은 경우 두 원소를 교환 2. 각 단계 수행 후 최대값이 마지막으로 이동하므로, 마지막 원소는 정렬대상에서 제외 3. 만약 끝까지 가면서 교환이 일어나지 않았으면 정렬이 되어 있는 것 #구현 #include using namespace std; void bubblesort(int* a, int n); void swap(int* a, int* b); int main(){ int n; cin>>n; int* a= new int[n]; for(int i=0; i>a[i]; bubblesort(a,n); for(int i=0; i