[고급알고리즘] 분할정복,정렬 알고리즘 총정리
알고리즘[중간고사정리]
- 분할정복 알고리즘
- 정렬 알고리즘
점근적 분석 가이드 —> 루프 or 중복루프
루프 → 루프의 수행시간은 구문 수행시간 x 반복 횟수 = 최대값
루프의 경우
1
2
3
4
// 루프의 경우
for(i=1; i<=n; i++)
m=m+2; //일정한 시간, c
전체 시간 = 상수 c × n = cn = O(n)
중복 루프의 경우
1
2
3
4
for(i=1; i<=n; i++) { //바깥 루프는 n번 수행
for( j=1; j<m; j++) //안쪽 루프 m번 수행
k=k+1; //일정한 시간, c
전체 시간 = c × n × n = cn^2 = O(n^2)
분할정복 알고리즘
분할정복 알고리즘 이란 ?
주어진 문제의 입력을 분할하여 문제 해결하는 방식의 알고리즘
한 문제를 유형이 비슷한 여러개의 하위 문제로 나누어 재귀적으로 해결하고 이를 합쳐 원래 문제로 해결
하위 문제를 재귀적으로 해결하기 때문에 하위 문제 각각은 원래 문제보다 범위가 작아야 하며 하위 문제는 각 문제마다 탈출 조건이 존재하여야함.
문제의 크기가 매우 큰 경우 사용
- 부분 문제는 더 이상 분할 할 수 없을때까지 분할
- 하향식 문제 풀이방식
분할 정복 알고리즘의 문제 해결 단계
입력을 둘 이상의 부분 문제로 분할 후 부분 문제를 더 작은 크기로 분할
더이상 분할할 수 없을때까지 분할 후 부분해를 구함
분할 정복 알고리즘의 기본
입력크기 n의 대한 총 분할횟수 k 입력크기가 n일때 더이상 분할 할수 없는 크기인 1이 되기 위한 분할 횟수
분할횟수 k의 값은 → k = bg_2n
분할 정복 알고리즘의 종류
- 합병
- 퀵
- 선택 알고리즘
- 최근접 점쌍
합병정렬은 지난번 블로그 글에 언급 해두었기 때문에 생략합니다.
합병정렬 → https://privateeye98.github.io/posts/mergesort/
퀵정렬(Quick Sort)
퀵정렬(Quick Sort)은 퀵이라는 이름답게 평균 속도 O(N*logN)을 자랑하는 매우 빠른 정렬 알고리즘이다. 퀵정렬은 분할정복(Divide & Conquer) 알고리즘의 하나로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하는 알고리즘이다.
퀵정렬의 전체적인 정렬 과정
- 퀵정렬은 임의의 pivot 값을 기준으로
- pivot 의 좌측에는 pivot 보다 작은값을 두고
- 우측에는 pivot 보다 큰 값을 두는 방식으로 정렬을 진행한다.
1
2
3
4
5
6
7
1. 리스트 안의 임의의 요소 하나를 선택한다. 이를 피봇(pivot) 이라고 하자.
2. pivot을 기준으로 pivot의 왼쪽에는 pivot보다 작은 원소를, pivot의 오른쪽에는 pivot보다 큰 원소를 배치한다.
3. pivot을 기준으로 분할된 왼쪽 리스트와 오른쪽 리스트에 대해 다시 1,2의 과정을 반복한다.
4. 이렇게 순환 과정을 통해 분할된 각 리스트의 크기가 0이나 1이 되면 수행을 종료한다.
자세한 과정
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1. 피봇을 선택한다.
2. left는 왼쪽에서 오른쪽으로 가면서 피봇보다 큰 수를 찾는다.
3. right는 오른쪽에서 왼쪽으로 가면서 피봇보다 작은 수를 찾는다.
4. 찾은 지점에서 left와 right를 교환한다.
5. 위의 2,3,4과정 left와 right가 교차할 때 까지 반복한다.
6. left와 right가 교차하면 피봇(pivot)과 right를 교환한다.
7. 이렇게 되면 피봇의 왼쪽에는 피봇보다 작은수가, 피봇의 오른쪽에는 피봇보다 큰 수가 위치한다.
8. 피봇을 기준으로 왼쪽과 오른쪽 리스트 두개로 나눠 위의 과정을 반복 수행한다.
9. 이렇게 순환 과정을 통해 분할된 리스트의 크기가 0이나 1이 되면 수행을 종료한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
int temp;
while (i <= j)
{
while (arr[i] < pivot) i++;
// arr[i] ≥ pivot 일 때까지, left에서 오른쪽 방향으로 탐색
while (arr[j] > pivot) j--;
// arr[j] ≤ pivot 일 때까지, right에서 왼쪽 방향으로 탐색
if (i <= j) // 큰 값이 작은 값보다 왼쪽에 있으면
{
// SWAP(arr[i], arr[j])
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}
정렬 알고리즘
- 선택정렬 → https://privateeye98.github.io/posts/selectsort/
- 버블정렬
- 삽입정렬
- 쉘정렬
- 힙정렬
- 기수정렬
선택정렬은 기존에 업로드 했기에, 넘어갑니다.
버블정렬
두개의 붙어있는 인덱스를 비교해서 앞으로 이동시키는 과정을 반복해서 정렬시키는 알고리즘
정렬하는 과정이 마치 거품처럼 위로 올라가는것 처럼 보여 붙여진 이름
다른 정렬 알고리즘에 비해 속도가 매우 느림 1번 정렬을 시행하는것을 pass라고함.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
void printArray(int A[], int n);
void BubbleSort(int A[], int n);
int main(void)
{
int arr[10] = {90, 20, 70, 60,55, 32, 47, 12, 88, 59};
printf("\nBefore sorting : ");
printArray(arr, 10);
BuubleSort(arr, 10);
printf("\n\nAfter sorting : ");
printArray(arr, 10);
printf("\n");
return 0;
}
void printArray(int A[], int n)
{
int i = 0;
for (i = 0; i<n; i++) {
printf("%2d ", A[i]);
}
printf("\n");
}
void BubbleSort(int A[], int n) {
int i, j, temp;
for (i = 0; i < n-1; i++) {
for ( j = 0; j < n-1-i ; j++) {
if (A[ j] > A[ j+1]) {
temp = A[ j];
A[ j] = A[ j+1];
A[ j+1] = temp;
}
}
}
}
삽입 정렬
배열을 정렬된 부분 (앞부분)과 정렬되지 않은 부분 (뒷부분)으로나누고, 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분의적절한 위치에 삽입하여 정렬하는 알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
int main()
{
int n, i, j, temp, a[5];
scanf("%d", &n); // 데이터 개수를 n에 입력받는다.
for (i = 0; i < n; i++) // 데이터 개수만큼 값을 a[]에 입력받는다.
{
scanf("%d", &a[i]);
}
// 삽입 정렬 시작
for (i = 1; i < n; i++) // 첫 시작은 2번째부터니 배열 인덱스 a[1]번부터 시작
{
temp = a[i]; // 삽입 값을 temp 변수에 저장
for (j = i-1; j >= 0; j--) // i-1번부터 처음까지 하나씩 비교하면서 넣으므로
{
if (a[j] > temp) // 비교값이 더 크면 한칸씩 당긴다.
{
a[j+1] = a[j];
}
else // 비교값이 더 작으면 삽입할 곳을 찾았으므로 멈춘다.
break;
}
a[j+1] = temp; // 삽입할 곳에 값을 넣는다.
}
// 삽입 정렬 끝났으므로 출력
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
시간복잡도는 O(n^2) 최적일댄 O(n)을 갖는다.
선택정렬과 버블정렬에 비해 우수하다
쉘 정렬
리스트를 일정한 간격(gap)에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다. 쉘 정렬은 삽입 정렬을 보완한 방법!
① 초기 시작 간격(gap)을 정한다. (간격을 k라고 하자.)
② k개씩 그룹으로 묶어 리스트를 나눈다.
③ 각 그룹의 n번째 원소들끼리 삽입 정렬을 수행한다. (1 ≤ n ≤ k)
④ k의 크기를 반으로 줄인다.
⑤ k가 1이 될 때까지 다시 ②부터 반복한다.
시간복잡도 : O(n^2) ~ O(n^1.250
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int main() {
int arr[] = {35, 33, 42, 10, 14, 19, 27, 44};
int n = sizeof(arr) / sizeof(arr[0]);
shellSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
힙정렬
고급 정렬 알고리즘(Merge, Quick, Heap) 중의 하나임.
이진 힙 트리구조를 사용하는 정렬 방법
합병 정렬(merge sort), 퀵 정렬(quick sort)과는 달리 힙 정렬은제자리 알고리즘(in place)
다른 조건에 비해 힙의 구조는 완전 이진트리여야 한다. 라는 조건이 있다.
힙의 루트에는 가장 높은 우선순위 (가장 큰 값)가 저장되어 있다.
시간 복잡도 : O(logN) → 전체데이터수가 N이라면 O(NlogN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
using namespace std;
//힙정렬
int n, heap[10000001];
void heapify(int i)
{
int cur = 2 * i;
if(cur < n && heap[cur] < heap[cur+1]) cur++;
if(heap[i] < heap[cur])
{
swap(heap[i],heap[cur]);
if(cur <= n/2) heapify(cur);
}
}
void heapsort(int i)
{
swap(heap[1],heap[i]);
int root = 1;
int cur = 2;
while(cur/2<i)
{
cur = 2*root;
if(cur < i-1 && heap[cur] < heap[cur+1]) cur++;
if(cur < i && heap[root] < heap[cur])
swap(heap[root],heap[cur]);
root = cur;
}
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",&heap[i]);
for(int i = n/2; i > 0; i--) // 최초 heap 생성
heapify(i);
for(int i = n; i > 0; i--) // heap 정렬
heapsort(i);
for(int j = 1; j <= n; j++) // 출력
printf("%d ",heap[j]);
}
기수정렬
양의 정수만을 정렬할 수 있는 특수한 정렬 방법으로 숫자를 부분적으로 비교하는 정렬 방법 – 분배 정렬
어느 비교 정렬 알고리즘보다 빠르다. 비교 연산이 없이도 정렬이 가능하다
시간복잡도 : 𝑂(𝑛𝑙𝑜𝑔 𝑛)을 뛰어 넘을 수 있는 유일한 알고리즘 → O(d*(n+k))
- d: 자릿수의 개수
- n: 데이터의 개수
- k: 자릿수 값의 범위 (일반적으로 10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <string.h>
void countingSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radixSort(arr, n);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
외부정렬
모든 정렬 알고리즘들은 내부 정렬
- 이는 입력이 주기억 장치 (내부 메모리)에 있는 상태에서 정렬이수행되기 때문
입력 크기가 매우 커서 읽고 쓰는 시간이 오래 걸리는보조 기억장치에 입력을 저장할 수밖에 없는 상태에서 수행되는 정렬
보조 기억 장치에서의 읽고 쓰기를최소화하는 것이 매우 중요.
외부정렬의 종류 - 균형 병합 , 계단식 병합,교대 병합 정렬, 다단계 병합 정렬, 2-way 병합, n-way 병합
시간복잡도 : O(log(N/M))
이진탐색
오름 차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
정렬된 자료를 반으로 나누어 탐색하는 방법 > 검색 원리상 반드시 정렬된 리스트에서만 사용가능
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int BinarySearch(int ar[], int target, int first, int last)
{
int mid = (first + last) / 2;
if (first > last)
return -1;
else {
if (ar[mid] > target) {
last = mid - 1;
BinarySearch(ar, target, first, last);
}
else if(ar[mid] < target) {
first = mid + 1;
BinarySearch(ar, target, first, last);
}
else return mid;
}
}
int main(void) {
int arr[] = { 7, 12, 13, 24, 33, 36, 42, 45, 49, 50, 51, 57, 61, 64, 65, 67, 71, 74, 86, 87, 98 };
int idx = 0, inputNum = 0;
int TRUE = 1;
while(TRUE) {
printf("찾고자 하는 숫자를 입력하세요. :");
scanf("%d", &inputNum);
idx = BinarySearch(arr, inputNum, 0, sizeof(arr) / sizeof(int) - 1);
if (idx == -1) {
printf("찾고자 하는 숫자가 없습니다. \n");}
else {
printf("Target Index : %d\n", idx);
TRUE = 0;
}
}
}