KyungHwan's etc.

기본알고리즘(Algorithm basic) 본문

Algorithm

기본알고리즘(Algorithm basic)

KyungHwan_0 2018. 6. 22. 14:11

기본알고리즘(Algorithm basic)

Bubble Sort

이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복 (마치 '거품’처럼 위로 올라감)

Bubble sort pseudo code

//크기가 n인 배열 A
for pass = 1 to n-1 // 총 n-1번을 비교해야 된다. (A[0]과 A[1], A[1]과 A[2] ...)
for i= 1 to n-pass // 오름차순이면 이미 정렬 한 뒷 쪽 얘들은 정렬하지 않아도 되니까.
if (A[i-1] > A[i])// 왼쪽의 원소가 오른쪽의 원소보다 크면
A[i-1] ↔ A[i]// 서로 자리를 바꿈
return 배열A

총 비교 횟수는 (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 이고 if문에서 바꾸는 시간복잡도는 O(1)이므로 전체 시간복잡도는 O(n^2) * O(1) = O(n^2)

Selection sort

배열 전체에서 최솟값을 '선택’하여 배열의 0번 원소와 자리를 바꾼다. 다음에 정렬할 때는 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여, 배열의 1번 원소와 자리를 바꾼다. 이런 식으로 반복한다.

Selection sort pseudo code

//크기가 n인 배열 A
for i= 0 to n-2{ // n-2까지 해야 밑의 for문에서 n-1까지 찾는다.
min = i // min에 0값을 대입시켜서 다음 값과 계속 비교하게 함.
    for j = i+1 to n-1{ // while ( j >= h) and (A[j-h] > CurrentElement) {
    // j값이 바뀌지 않는 이상 왼쪽은 무조건 성립하고 오른쪽이 비교하는 것! 간격만큼의 값보다 큰지 작은지. 만약 왼쪽에 있는 원소가 더 크면
    A[i]~A[n-1]에서 최솟값을 찾음
        if (A[j] < A[min]) //min값이 그 다음 값보다 크면
        min = j //min을 그 다음 값으로 바꿔줌.
    }
A[i] ↔ A[min] // min의 원소 값과 처음에 했던 i값과 바꿈.
}
return 배열A

총 비교 횟수는 : (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 이고 if문에서 바꾸는 시간복잡도는 O(1)이므로 전체 시간복잡도는 O(n^2) * O(1) = O(n^2)

Insertion sort

배열을 정렬된 부분(앞 부분)과 정렬 안 된 부분 (뒷 부분)으로 나눈다. (맨 처음에 첫 번째 원소는 정렬 되어있고 두 번째 원소부터 정렬 안 되어있다고 생각하면 쉽다.) 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 가장 오른쪽 원소와 비교하는데 정렬 안 된 부분의 가장 왼쪽 원소가 정렬된 부분의 가장 오른쪽 원소보다 작으면 정렬 된 부분의 가장 오른쪽 원소가 오른쪽으로 한 칸 씩 옮겨진다. 그러다가 그러지 않는 곳이 있으면 그곳에 정렬 안 된 부분의 가장 왼쪽 원소를 넣는다.

Insertion sort pseudo code

//크기가 n인 배열 A
//얘도 bubble sort와 마찬가지로 정렬된 부분과 정렬 안 된 부분 기준이므로. n-1번
for i=1 to n-1 { 
CurrentElement= A[i] // 정렬 안 된 부분의 가장 왼쪽 원소를 element에 따로 넣음
j ← i-1// 정렬된 부분의 가장 오른쪽 원소 인덱스를 j에 넣음
    while (j >= 0) and (A[j] > CurrentElement) {
    // j가 0보다 작으면 마이너스 인덱스라 안 되고 거기까지 비교해야 되니까, 정렬된 부분의 가장 오른쪽 원소가 정렬 안 된 부분의 가장 왼쪽 원소보다 크다면
    A[j+1] = A[j] // 바로 오른쪽에 정렬된 부분의 가장 오른쪽 원소값을 대입시켜서 오른쪽으로 옮겨버림
    j ← j-1 //그리고나서 j를 하나 깎고 다시 while문으로.
    }
A [j+1] ← CurrentElement // A[j]가 더 작으니까 그 다음 자리가 비었을 테니 거기다가 element를 넣어줌.
}
return A

총 비교 횟수는 : (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 이고 if문에서 바꾸는 시간복잡도는 O(1)이므로 전체 시간복잡도는 O(n^2) * O(1) = O(n^2)

Shell sort

bubble sort와 insertion sort의 단점을 보완함. 배열 뒷 부분의 작은 숫자를 앞 부분으로 이동시키고 동시에 앞 부분의 큰 숫자는 뒷 부분으로 이동시키고. 간격이 1일 때는 삽입 정렬을 수행한다.

간격을 설정하고 그 다음 간격은 더 작게 설정한다. 그리고 마지막에는 간격을 1로 놓고 수행한다. 쉘 정렬의 수행 속도는 간격 선정에 따라 좌우 된다.

Shell sort pseudo code

for each gap h = [ h0> h1> ... > hk=1]
//갭을 지정한다. for문을 써서 /2를 해 계속 낮춰줄 수 있다. 마지막은 1이라 삽입정렬이 되도록.
    for i = h to n-1{
    //h부터 n-1까지. 밑에 j-h가 있어서 h이면 0이되기 때문에 간격만큼 비교하는 게 된다.
    CurrentElement = A[i] ; //차례대로 current에 넣는다. 바꿔주려고.
    j = i ; // 위와 동일한 인덱스를 주기 위해서 i를 j에 넣음.
    while ( j >= h) and (A[j-h] > CurrentElement) {
    // j값이 바뀌지 않는 이상 왼쪽은 무조건 성립하고 오른쪽이 비교하는 것! 간격만큼의 값보다 큰지 작은지. 만약 왼쪽에 있는 원소가 더 크면
    A[j] = A[j-h]; //오른쪽 원소에 왼쪽 원소를 넣는다.
    j ←j-h; //오른쪽 원소 인덱스를 왼쪽 원소 인덱스로 바꿔준다. 얘가 간격만큼 빠지니까 그 다음도 간격만큼 빠지는 값을 봐야 된다. j >= h가 만족하고 A[j-h] > current면 또 바꿔줄 수 있다.
    }
A[j] ←CurrentElement; //그러면 바로 currnet를 A[j]에 넣어줌으로써 완전히 바뀌게 된다.
}
return A

최악의 경우 시간복잡도 : O(n^2)

최선의 경우 시간복잡도 : O(nlogn)

쉘 정렬의 시간복잡도는 아직 풀리지 않은 문제다. 쉘 정렬은 입력 크키가 크지 않은 경웨 매우 좋은 성능을 보인다. 보통 Embedded 시스템에서 주로 사용한다.

Heap sort

힙 조건 (각 노드의 값이 자식 노드의 값보다 커야/ 작아야 함) 을 만족하는 완전 이진 트리(트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태). 노드들을 빈 공간없이 배열에 저장한다. 힙의 루트에는 우선순위가 가장 높은 값이 저장됨. (가장 큰 값 또는 가장 작은 값)

힙에서 부모 노드와 자식 노드의 관계

  1. A[0]은 비우고 A[1] ~ A[n]까지 힙 노드들을 트리의 층별로 좌에서 우로 배열에 저장한다.

  2. A[i]의 부모노드 = A[i/2]

  3. A[i]의 왼쪽 자식 노드 = A[2i]

  4. A[i]의 오른쪽 자식 노드 = A[2i + 1]

오름차순 정렬 시

힙의 루트에는 가장 큰 수가 저장된다. 그리고 루트의 숫자를 힙의 가장 마지막 노드에 있는 숫자와 바꾼다. 바꾼 마지막 노드의 숫자가 힙 조건에 위배되면 힙 조건을 만족시켜야 하니 밑의 자식들 중에서 큰 자식과 바꾸고(DownHeap()), 루트를 고정시키기 위해 힙 크기를 1개 줄이는 식으로 해서 반복한다. .

Heap sort pseudo code

heapSize = n // heapSize: 힙크기
for i = 1to n-1
A[1] ↔ A[heapSize]// 루트와힙의마지막노드교환
heapSize = heapSize-1// 힙의크기를1 감소
DownHeap()// 위배된힙조건을만족시킴
return 배열A

Heap sort C code

#include <stdio.h>
#include <string.h>
#pragma warning(disable:4996)
​
void DownHeap(int *arr, int i) {
    int j, n, temp, flag = 1;
    n = arr[0];
    while ((i * 2 <= n) && (flag == 1)) {
        j = i * 2; //왼쪽 자식의 인덱스
        if ((j + 1 <= n) && (arr[j] < arr[j + 1]))
            j = j + 1; //오른쪽 자식의 인덱스
        if (arr[j] < arr[i])
            flag = 0;
        else {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i = j;
        }
    }
}
​
void BuildHeap(int *arr) { //빅오의 n으로 볼 수 있다.
    int i, n;
    n = arr[0]; //그대로 main함수에 있던 n. 즉, size가 들어간다.
    for (i = n / 2; i >= 1; i--) //n의 반 만큼 횟수를 지정. 이유는 노드가 그 만큼이기 때문에 9개면 4번 실행하면 되니까.
        DownHeap(arr, i); //4,3,2,1 순서로 실행해준다. 즉, 완전 이진트리인지 확인하는 거.
}
int main(void) {
    int n, A[20], i, j, last, temp;
    printf("array size : ");
    scanf("%d", &n);
    printf("\n input the array : ");
    for (i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    A[0] = n; //아예 사이즈를 A[0]에다 넣고있음.
    BuildHeap(A); //BuildHeap함수 실행
    printf("\n max heap \n");
    for (i = 1; i <= n; i++)
        printf("%d", A[i]);
    while (A[0] > 1) {
        last = A[0]; //사이즈(끝값)를 last에 넣음
        temp = A[1]; //끝 값과 Root를 바꿔주는 과정
        A[1] = A[last]; 
        A[last] = temp; 
        A[0]--; //그리고 heap을 하나 줄여주기 위함. 9에서 8으로...
        DownHeap(A, 1); //8,1을 넣어서 실행시킴. 그리고 나오면 다시 반복.
        printf("\n\n middle value result \n");
        for (i = 1; i <= n; i++)
            printf(" %d", A[i]);
    }
    printf("\n ** array result ** \n");
    for (i = 1; i <= n; i++)
        printf("%d", A[i]);
    getchar();
    return 0;
}

Divide and Conquer Algorithm

주어진 문제의 입력을 분할하여 문제를 (정복)해결하는 방식. 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래의 해를 얻음.

부분 문제는 더 이상 분할할 수 없을 때까지 분할함.

크기가 n인 입력을 3개로 분할한 경우(각 분할된 부분 문제의 크기) -> n/3(입력 크기가 1인 경우, 더 이상 분할하지 않음)

입력 크키가 n일 때 총 몇 번을 분할하면 더 이상 분할할 수 없는 크기인 1이 될까? -> 총 분할한 횟수를 k, 1/2씩 분할된다고 하면… 1번 분할했을 때 n/2, n/2^2, n/23…n/2k가 된다. n/2^k가 = 1일 때 더 이상 분할할 수 없다.

Merge Sort

Merge sort는 분할 정복 알고리즘으로 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자들로 합치는 것이다.

입력을 2개의 부분 문제로 분할, 부분 문제의 크기가 1/2로 동일하게 감소한다. (재귀적으로 나눌 수 없을 때까지 분할) -> 각각의 부분 문제를 재귀적으로 합병하여 정렬(정복)한다.

Merge sort pseudo code

MergeSort(A,p,q)
입력: A[p]~A[q] //
출력: 정렬된A[p]~A[q]
if ( p < q ) { // 배열의 원소의 수가 2개이상이면 //어차피 p에 0이 들어가고 q에 n-1이 들어가기 때문에 저 공식을 써도 됌.
k = (p+q)/2 // k; 반으로 나누기 위한 중간 원소의 인덱스
MergeSort(A,p,k) // 앞 부분 재귀호출
MergeSort(A,k+1,q) // 뒷 부분 재귀호출
Merge(A, p, k, q) // A[p]~A[k]와A[k+1]~A[q]를 합병함
}

Merge sort C code

#include<stdio.h>
#pragma warning(disable: 4996)
#define MAX 50
​
void merge(int*, int, int, int);
​
void mergeSort(int*, int, int);
​
int main(void) {
    int A[MAX], i, n;
    printf("array size : ");
    scanf("%d", &n);
    printf("\n input the array : ");
    for (i = 0; i < n; i++)
        scanf("%d", &A[i]);
    
    mergeSort(A, 0, n-1); //mergeSort함수로 감.
    
    printf("\n <array result>\n");
    for (i = 0; i < n; i++)
        printf("%d ", A[i]); //A배열을 출력함.
    
    getchar();
    return 0;
}
​
void merge(int A[], int low, int mid, int high) {
    int i, m, k, l;
    int temp[MAX]; //temp는 A와 크기가 같아야 함. 공간을 따로 둬야된다. 똑같은 게 있어야됌
    l = low; //처음부터 확인
    i = low; //temp의 처음부터 시작해야되니까
    m = mid + 1; //mid의 바로 다음 것부터 시작. (중간 다음부터 비교를 해야되니까.)
    while ((l <= mid) && (m <= high)) {
//맨 처음이 중간을 지났냐?, 중간다음이 맨 끝을 지났냐?
        if (A[l] <= A[m]) { //인덱스가 아니라 원소다 착각하지말자. 맨 처음과 중간 다음을 비교함.
            temp[i] = A[l]; //맞으면 천천히 대입하면서 증가시킨다.
            l++; //증가시키고 다시 돌린다. 대입했으니 그 다음으로.
            printf("LEFT : temp[%d]=%d\n", i, temp[i]);
        }
        else {
            temp[i] = A[m]; //만약 m쪽이 더 작으면 그걸 다음 원소에 넣어줘야지.
            m++; //증가시켜주고.
            printf("RIGHT : temp[%d]=%d\n", i, temp[i]);
        }
        i++; //다음 원소 바꾸거나 넣어주려고.
    }
    if (l > mid) { //왼쪽 부분은 다 했으니까 m이 커졌던 부분에서부터 오른쪽 값을 temp에 복사
        for (k = m; k <= high; k++) { //mid+1을 넣고 high까지
            temp[i] = A[k];
            i++;
            printf("RIGHT : temp[%d]=%d\n", k, temp[i-1]);
        }
    }
    else { //오른쪽 부분이 완료됐으니 커진 l에서부터 왼쪽 값을 temp에 복사
        for (k = l; k <= mid; k++) { // l을 증가시키면서 그 원소값을 넣어줌.
            temp[i] = A[k];
            i++;
            printf("LEFT : temp[%d]=%d\n", high, temp[i-1]);
        }
    }
    printf("RESULT : ");
    for (k = low; k <= high; k++) {
        A[k] = temp[k]; //temp에다 넣어줬던 걸 다시 A[]에 넣는 과정.
        printf("%d ", A[k]); //이제 merge가 하나 끝난 것.
    }
    printf("\n\n");
}
​
void mergeSort(int A[], int low, int high) { //(A, 0, n-1)을 받음.
    int mid;
    if (low < high) { //어차피 0, n-1이니까 갯수 확인 하는 용도.
        mid = (low + high) / 2; //계속 반을 나눔.
        mergeSort(A, low, mid); //재귀로 여기서 계속 들어감. 나누고 나누고 나누고...
        //그러다보면 low와 mid가 같아질 때가 있다. mergeSort(A, 0, 1)가 될 때 mergeSort(A, 0, 0)이 됌.
        //그러면 다시 하나하나씩 빠져나온다.빠져나오기 시작함.
        mergeSort(A, mid + 1, high); //mergeSort(A, 0, 1)에서 한번 더 들어가면
        //mergeSort(A, 0, 0) + mergeSort(A, 1, 1)가 나오고 둘다 안되므로 merge를 실행
        merge(A, low, mid, high); //merge(A, 0, 0, 1)을 실행.
        //A[p]~A[k]와A[k+1]~A[q]를 합병함
    }
}

생각보다 헷갈렸다. 많이. 가령 5 1 9 2 7을 정렬한다고 치면 반으로 가르니까 5 1 9와 2 7로 나눠지고 3이면 1이니 1인덱스니까 5 1을 합병정렬해야된다. 1 5가 되고 그 다음에는 1 5 9. 그다음에는 2 7 그 다음에야 1 2 5 7 9가 된다.

시간복잡도

합병 정렬의 시간복잡도는 층 수 * (각 층에서의 시간복잡도)이다.

입력 크기가 n이라고 치면 n을 1/2로 계속 나누다가 더 이상 나눌 수 없는 1이 될 때 분할을 중단한다.n을 1/2로 k번 분할했을 때 1이므로 n=2^k로 k=logn이다. 각 층마다 n개의 원소가 복사되므로 O(n*logn)이다.

  • O(n) = O(nlogn)이다.

연결 리스트에 있는 데이터를 정렬할 때 효율적임, 외부정렬의 기본이 된다.

Quick Sort

문제를 2개의 부분문제로 분할, 각 부분문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘이다.

피봇(pivot)이라 일컫는 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고 피봇을 그 사이에 놓는다.

퀵 정렬은 분할된 부분문제들에 대해 동일한 과정을 재귀적으로 수행하여 정렬한다.

Quick sort c code

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      //pivot을 중간으로 선택.
      int pivot = arr[(left + right) / 2];
      int temp;
      do {
        while (arr[i] < pivot) //pivot보다 작으면 계속 증가
            i++;
        while (arr[j] > pivot) //pivot보다 크면 계속 감소
            j--;
        if (i <= j) {   //빠져나온 것에서 서로 비교해서 바꾼다.
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    } while (i<= j);
​
    /* recursion */
    if (left < j)   //left 값보다 작아질 때까지 재귀함수를 돌린다.
        quickSort(arr, left, j);
​
    if (i < right)
        quickSort(arr, i, right);
}}

시간복잡도

퀵 정렬의 성능은 피봇 선택이 좌우한다. 피봇으로 가장 작은 숫자 또는 가장 큰 숫자가 선택되면, 한 부분으로 치우치는 분할을 야기한다.

최선의 경우 시간복잡도 : O(n)

각 층에서 비교 횟수 : O(n) ->각 원소가 각 부분의 피봇과 1회씩 비교됨.총 비교 횟수 = O(n) * (층수) = O(n) * (n)

평균의 시간복잡도는 최선의 경우와 같다. O(n) 피봇을 항상 랜덤하게 선택한다고 가정했을 때. 최악의 경우에는 O(n^2)가 나온다. 퀵 정렬은 많은 입력에 대해 가장 좋은 성능을 보인다. 삽입정렬이 같이 사용되면 성능을 높일 수 있다.

Greedy Algorithm

입력 데이터 간의 관계를 고려하지 않고 수행 과정에서 ‘욕심내어(greedy)’ 최소값 또는 최대값을 가진 데이터를 선택한다.

경우의 수를 모두 분석해서 부분적인 최적해를 찾고, 이들을 모아서 전체 문제의 최적해를 얻음.

선택한 데이터를 버리고 다른 걸 취하지 않음. 이러한 특성때문에 대부분의 그리디 알고리즘은 매우 단순하며, 제한적인 문제들만이 그리디 알고리즘으로 해결된다.

동전 거스름돈 문제

가장 간단하고 효율적인 방법 -> 남은 액수를 초과하지 않는 조건하에 욕심내어 가장 큰 액면의 동전을 취함.

#include<stdio.h>
#pragma warning(disable: 4996)
​
int main(void) {
    int change, W;
    int n500 = 0, n100 = 0, n50 = 0, n10 = 0, n1 = 0;
    printf("input the 거스름돈 : ");
    scanf("%d",&W);
    change = W;
    while (change >= 500) {
            change = change - 500;
            n500++;
        }
    while (change >= 100) {
        change = change - 100;
        n100++;
    }
    while (change >= 50) {
        change = change - 50;
        n50++;
    }
    while (change >= 10) {
        change = change - 10;
        n10++;
    }
    while (change >= 1) {
        change = change - 1;
        n1++;
    }
    printf("500 number is : %d coin\n", n500);
    printf("100 number is : %d coin\n", n100);
    printf("50 number is : %d coin\n", n50);
    printf("10 number is : %d coin\n", n10);
    printf("1 number is : %d coin\n", n1);
    printf("coin number : %d coin\n", n500 + n100 + n50 + n10 + n1);
    getchar();
    return 0;
}

500원짜리 동전을 처리할 때 다른 동전을 거슬러 주는 것에 대해 전혀 고려하지 않는다.

그래서 항상 최소 동전 수를 계산하지는 못 함. 만약 160원짜리 동전이 있고 거스름돈이 200원이면 100원보다 큰 160원 + 10원*4개라서 총 5개인데 중간에 있는 100원만 쓰면 2개로도 가능하다.

Reference

http://qssdev.tistory.com/50


'Algorithm' 카테고리의 다른 글

마방진 알고리즘(홀수)  (1) 2019.01.23
'Algorithm' Related Articles more
Comments