[ 정렬들(Selection, Insertion, Bubble, Quick, Merge, Heap, Radix)에 대하여

수행시간, 비교 횟수, Swap횟수를 통한 비교 ]

1) Selection Sort :

분석 : 데이터의 개수가 n개 일 때, 최소값을 선택하는 데 걸리는 시간 = O( n )

-> 최솟값을 선택하여 리스트의 첫 번째 요소와 자리를 바꾼다.

안정성을 만족하지 않고, 전체 시간복잡도는 O( n^2 )을 따른다.

데이터를 0부터 n까지 매번 비교해야 하므로, n(n-1)/2 번 비교하게 되며 O( n^2 ) 이 되고,

Swap횟수는 찾은 최소값과 리스트의 첫 번째 요소와 바꿔주면 되므로, n-1번 수행되어 O( n ) 이 된다.

2) Insertion Sort :

분석 : 리스트의 값들을 순회하며 리스트에서 정렬이 필요한 데이터는 적당한 곳에 삽입해나간다.

정렬되어 있는 부분에 새로운 레코드를 적절한 위치에 삽입해야하는 과정을 반복해야 한다.

안정성이 보장되고 이미 정렬되어있으면 O(n)이 되어 효율적이지만, 삽입하는 과정이 있으므로 데이터가 많고 정렬이 되어있지 않다면 비효율적이다.

Worst Case는 데이터가 역순으로 정렬되어 있는 경우이며, 비교 횟수는 매번 데이터들의 값을 비교하여 위치를 옮겨주는 과정을 수행해야 하므로, n(n-1)/2 번 비교하며,

Swap은 데이터를 매번 비교하여 이동하는 횟수( n(n-1)/2 ) 에, 데이터가 n개일 때, 처음 인덱스에 대하여 n-1번 만큼 수행해야 하므로 n(n-1)/2 +(n-1) = O( n^2 ) 이 되고, 결과적으로 비교 횟수와 Swap횟수 둘 다 O( n^2 )이 된다.

3) Bubble Sort :

분석 : 인접한 리스트의 요소를 매번 비교해야 하고, 비교 시마다 인접한 요소가 정렬이 되어 있지 않다면 Swap을 해야하므로, 비교 횟수의 경우에는 항상 n(n-1)/2 번 비교하게 되며,

Swap의 경우에는 Best Case의 경우에는 이미 정렬되어 Swap하지 않아도 되는 경우이므로 0이지만, Worst Case의 경우일 때에는 비교와 같이 n(n-1)/2 번 수행해야 하므로, 비교 횟수와 Swap횟수 둘 다 O( n^2 ) 이 된다.

4) Quick Sort :

분석 : 평균적으로 가장 빠르다고 알려져 있는 정렬방법이다. 리스트를 O( n )만큼 추가적으로 할당하여 정렬하는 방법이 있긴 하지만 Stable하고 In-place하지 않으므로 보통은 추가적인 메모리를 더 필요로 하지 않는 방법을 사용한다.

pivot값을 세우고, 이 pivot값을 기준으로 왼쪽과 오른쪽을 분할하여 각각의 부분을 다시 재귀적으로 정렬하는 방법이다.

(pivot 값을 median, 즉 리스트의 중간 값으로 설정하게 되면 Worst case를 피할 수 있는 확률이 더 높아지기 때문에 효율이 높아지게 된다.)

Best Case는 왼쪽과 오른쪽 분할된 부분의 크기가 거의 균등하게 분할되는 경우이며, 분할된 Level의 크기는 logn 이며, 각 분할된 부분에 대하여 비교를 수행하는 횟수는 n 이므로, 비교 횟수는 O(logn) 이 된다.

그러나 Worst Case의 경우에는 왼쪽과 오른쪽이 불균등하게(한쪽은 1개, 한쪽은 n-1개) 분할되는 경우이며,

분할된 Level의 크기가 n 이 되고, 분할된 부분에 대하여 비교를 수행하는 횟수는 n 이므로 총 비교 횟수는 O( n^2 ) 이 되고, Swap횟수는 분할된 부분에 대하여만 Swap을 수행하면 되므로 비교 횟수보다 항상 적다.

5) Merge Sort :

분석 : 리스트를 두 개로 분할하는 과정을 재귀적으로 수행한 후, 다시 올라오며 각각을 정렬하며 합쳐지는 과정을 수행한다. 분할할 때에는 정렬을 하지 않으며, 전부 분할 한 후에 다시 분할된 부분을 합치며 정렬을 수행하는 방식이다.

Best Case, Worst Case에 관계없이 퀵 정렬의 이상적인 분배를 위하여 항상 균등 분할을 하게 되며, 분할된 Level의 크기는 logn 이 되며, 각 분할된 부분에서 n 번의 비교가 수행된다. 따라서 비교 횟수는 O(nlogn) 이 된다.

Swap의 경우 각 분할된 부분에서 ( n *2)번의 Swap이 수행되므로 비교 횟수는 O(nlogn) 이 된다.

6) Heap Sort:

분석 : Heap에서는 각 노드는 자식 노드의 값보다 작으면 안 된다는 성질을 가지고 있다.

n개의 노드에 대하여 완전이진트리는 log(n+1) 의 Level을 가지므로 평균 시간복잡도는 O( nlogn )이 되며,

최악의 경우에 비교는 매번 Heapify를 통해 힙을 재구성 하는 부분에서 Level의 크기( logn )에 대하여 n번 비교를 하게 되므로, O( nlogn )이 되고, Swap횟수는 heapify에서 매번 Swap이 일어나는 경우에, 루트노드와 마지막 노드를 바꿔주는 수행 횟수도 더해주어야 하므로, O( nlogn ) + O(n) = O( nlogn ) 이 된다.

7) Radix Sort:

분석 : 리스트의 전체를 비교하는 것이 아니라, 자리 수를 이용하여 정렬하는 방법이다.

현재 일반적인 정렬 방법의 가장 효율적인 시간복잡도는 O( nlogn )이지만, 이것보다 더 좋은 효율을 낼 수 있는 방법이기도 하지만, 정렬할 수 있는 타입이 숫자와 같이 제한적이라는 단점이 있고, 큐 방식을 이용하여 자릿수에 따라 분할하기 때문에 비교나 Swap횟수는 따로 수행하지 않아 0이 된다.

아래의 그림은 테스트 데이터(정수)의 갯수 n을 각각 100개, 1000개, 10000개, 50000개로 했을 때의 Swap횟수와 비교횟수, 수행시간의 데이터이다.

Algorithm 메뉴에 포스팅했던 백준 알고리즘 문제들에 대하여,

예전에 알고리즘을 처음 해보기 시작할 때 문제풀어보기에 급급히 작성했던 코드들이어서 

부족한 코드도, 수정해야하는 코드도 많은데 보완없이 그대로 올렸던 터라 많이 고쳐야 할 것 같습니다.

최근 블로그 활동을 많이 못하게 되었는데, 조만간 전체적인 코드 수정과 함께 

시간이 된다면 추가적으로 문제들을 더 올려보도록 노력하겠습니다.

백준 알고리즘 - 10828번 스택 문제입니다.

(참고 - https://www.acmicpc.net/problem/10828 )

코드)

#include <stdio.h>

#include <string.h>

int stack[10000];

int main() {

int N, i, j, num, top=0;

scanf("%d", &N);

for(i=0; i<N; i++) {

char cmd[BUFSIZ];

scanf("%s", cmd);

if(strcmp(cmd, "push") == 0) {

scanf("%d", &num);

stack[top] = num;

top++;

}

if(strcmp(cmd, "pop") == 0) {

if(top <= 0)

printf("-1\n");

else {

printf("%d\n", stack[top-1]);

top--;

}

}

if(strcmp(cmd, "size") == 0) {

printf("%d\n", top);

}

if(strcmp(cmd, "empty") == 0) {

if(top <= 0)

printf("1\n");

else

printf("0\n");

}

if(strcmp(cmd, "top") == 0) {

if(top <= 0)

printf("-1\n");

else 

printf("%d\n", stack[top-1]);

}

}

return 0;

}

- 문제에 맞게 C로 스택함수를 직접 구현해주면 되는 부분입니다.

다른 부분은 생략하고, 각 명령부분들만 살펴보도록 하겠습니다.

먼저 입력받은 문자열 cmd가 PUSH인지 아닌지 파악하기 위해 문자열 비교함수인 strcmp를 이용하여 push와 비교를 하고, push일 경우 숫자도 함께 입력받도록 하여 배열 stack의 인덱스 top에 넣어주고, top은 1 증가시켜줍니다.

입력받은 문자열이 POP이라면, top의 인덱스를 먼저 비교하여 0보다 작거나 같을 시에는 stack에 아무 값도 현재 들어가있지 않다는 것을 의미하므로 문제의 조건에 따라 -1을 출력하고, top이 0보다 클 경우 값이 있다는 것이므로 stack의 인덱스 top-1의 값을 출력한 뒤, top을 1 감소시켜줍니다.

입력받은 문자열이 size라면, top을 출력해줍니다.(인덱스 top이 곧 stack의 size를 가리키므로)

입력받은 문자열이 empty라면, top의 값을 비교하여 0 또는 1을 출력해줍니다.

입력받은 문자열이 top이라면, top의 값을 비교하여 0 또는 stack의 인덱스 top-1 (가장 위에 있는 값 = 가장 마지막에 push된 값)을 출력해줍니다.

백준 알고리즘 - 10817번 세 수 문제입니다.

(참고 - https://www.acmicpc.net/problem/10817 )

코드(1) - 변수의 단순비교 조건 이용

#include <stdio.h>
int main() {

int num1, num2, num3;

scanf("%d %d %d", &num1, &num2, &num3);

if(num1 > num2) {

if(num1 > num3) {

if(num2 > num3) printf("%d", num2);

else printf("%d", num3);

}

else printf("%d", num1);

}

else {

if(num2 > num3) {

if(num1 > num3) printf("%d", num1);

else printf("%d", num3);

}

else printf("%d", num2);

}

return 0;

}

코드(2) - 배열을 이용한 비교

#include <stdio.h>

int main() {

int arr[3], i, j, tmp;

scanf("%d %d %d", &arr[0], &arr[1], &arr[2]);

for(i=0; i<3; i++)

for(j=0; j<2; j++)

if(arr[j] >= arr[j+1]) {

tmp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = tmp;

}

printf("%d\n", arr[1]);

return 0;

}

- 코드를 두 가지로 올린 것은 문득 두 방법의 차이를 비교하며 설명하고 싶었기 때문입니다.

코드(1) 의 결과

코드(2) 의 결과

두 가지 방법의 차이를 파악하셨나요.

첫번째 코드의 경우에는 단순히 일일이 비교해가며 조건을 설정하였기 때문에 코드의 길이는 길어질수밖에 없는 대신 변수만을 이용하기 때문에 메모리의 크기는 상대적으로 적게 잡아먹게 됩니다.

그에 반하여 두번째 코드의 경우에는 배열을 추가적으로 사용하기 때문에 메모리를 상대적으로 더 잡아먹게 되는 대신 코드의 길이는 비약적으로 줄일 수 있습니다.

이러한 두 가지 차이와 더불어 가장 중요한 '시간'에 대한 부분은 사실 너무 적은 케이스이기 때문에 차이가 안나는 것 처럼 보이지만, 만약 세 수에 대한 비교가 아니라 매우 많은 수들에 대한 비교라면 똑같은 방법을 취했을 때에는 코드(2)의 정렬을 이용하여 계산하는 시간이 더 걸릴 것입니다. 코드(1)의 경우에 for문을 이용하지 않기 때문이죠.

다만, 코드(1)의 방법으로는 상상할 수 없을만큼 코드길이가 길어질 것입니다. 간단한 문제가 아닌 이상에야 단순비교만큼 무식한 방법이 없...겠죠?

이러한 방법들을 비교해가며 차이를 조금 더 피부로 느끼면 어떨까해서 올려보았습니다.

사실 문제에 적합한 비교예시는 아니었던 것 같습니다.. ( _ _ ) 그냥 정말 문득생각나서....

백준 알고리즘 - 10808번 알파벳 개수 문제입니다.

(참고 - https://www.acmicpc.net/problem/10808 )

 코드 )

#include <stdio.h>

#include <string.h>

int main() {

char arr[BUFSIZ];

int tmp[BUFSIZ], cnt[BUFSIZ]={0,};

int i, j;

scanf("%s", arr);

for(i = 0; i < strlen(arr); i++)

tmp[i] = arr[i] - 97;

for(i = 0; i < strlen(arr); i++)

for(j = 0; j < 26; j++)

if(tmp[i] == j)

cnt[j]++;

for(i=0; i < 26; i++)

printf("%d ", cnt[i]);

printf("\n");

return 0;

}

- 길이를 계산하는 것이 귀찮아서.. strlen함수를 사용하려고 string.h 를 추가하였습니다.

먼저 char형 배열 arr에 문자열을 입력받습니다. 다음으로 char형 배열의 길이를 계산하여 길이만큼 반복합니다.

arr의 인덱스 0부터 차례대로 arr[0]-97을 하여 int형 배열 tmp에 저장하게 되면, 아스키코드를 참고하면 문자 a는 정수 97입니다. 

즉 a - 97을 하게되면 정수로 0 이 됩니다. 이를 이용하여 arr[0] - 97을 한 후 int형 배열에 저장하게 되면 1의 값이 tmp[0]에 저장됩니다. (arr[0]이 b 이므로)

이와 같은 방법으로 tmp배열에 문자를 숫자로 바꾸어 저장해줍니다.

이후에 다시 한 번 for문을 이용하여 문자열의 길이만큼 반복을 하는데, 내부 for문에서는 알파벳의 총 문자의 갯수가 26개 이므로 (a~z) tmp에 저장된 값과 j를 비교하며 같다면 cnt의 해당 인덱스에 카운트를 누적하여 더해줍니다.

(알기 쉽게 예를 들면 처음에 cbab라는 문자열을 입력받았다면, tmp[0]=2, tmp[1]=1, tmp[2]=0, tmp[3]=1 라는 값이 들어 있을 것입니다. 그리고 배열 cnt에는 cnt[0]=1, cnt[1]=2, cnt[2]=1 의 값이 저장될 것입니다.)

최종적으로 배열 cnt에 저장된 값들을 출력해주면 됩니다.

백준 알고리즘 - 10798번 세로읽기 문제입니다.

(참고 - https://www.acmicpc.net/problem/10798 )

코드 )

#include <stdio.h>

#define MAX_SIZE 15

char str_read[5][MAX_SIZE];

int main() {

int i, j;

for(i=0; i<5; i++) {

scanf("%s", str_read[i]);

}

for(j=0; j<MAX_SIZE; j++) {

for(i=0; i<5; i++) {

if(str_read[i][j] == NULL)

continue;

else

printf("%c", str_read[i][j]);

}

}

printf("\n");

return 0;

}

- 먼저 char형 2차원 배열 str_read[5][15] 를 생성합니다. 그 후 배열 str_read에 문자열을 5번 입력받아서 각각 저장합니다.

그 후, str_read[0][0]의 문자를 먼저 하나 출력해줍니다. 다음으로 str_read[1][0]의 문자를 출력하고,

그 다음엔 str_read[2][0] 의 문자를 , 이와 같이 i열의 문자 먼저 출력해 준 뒤, 

다음으로 j열의 인덱스를 1 증가시켜서 str_read[1][0] -> str_read[2][1] -> str_read[3][1] -> ... 와 같이 출력해주면 세로로 읽기가 됩니다.

만약 이 때 빈 공간, 즉 NULL을 만나게 되면 다음으로 건너뛰어서(continue) 계속 진행하면 됩니다.

핵심은 굳이 2차원배열의 세로값들을 따로 제2의 배열을 만들고 옮기는 복잡한 과정을 통해 한번에 출력할 생각을 하지말고, 문자 하나씩 이동하며 바로바로 출력하면 손쉽게 된다는 것입니다.

백준 알고리즘 - 9012번 : 괄호 문제입니다.

(참고 - https://www.acmicpc.net/problem/9012 )

코드 ) 

#include <stdio.h> 

#define MAXSIZE 50

int main() {

    int i, j, cnt, num;

    char arr[MAXSIZE];

    scanf("%d", &num);

    for ( j = 0; j < num; j++) {

        cnt = 0;

        scanf("%s", arr);

        for ( i = 0; i < MAXSIZE; i++) {

            if ( arr[i] == '\0')

                break;

            if ( arr[i] == '(')

                cnt++;

            else if ( arr[i] == ')' && cnt > 0)

                cnt--;

            else if ( arr[i] == ')' && cnt <= 0) {

                cnt--;

                break;

            }

        }

        if ( cnt == 0 )

            printf("YES\n");

        else

            printf("NO\n");

    }

}

- 어려워보일수도 있지만, 생각해보면 간단한 문제입니다. 먼저 문자열을 char형 배열에 입력받습니다.

char형은 각 주소번지마다 1Byte만큼 저장할 수 있으므로 '(' 혹은 ')' 문자 하나하나가 각 인덱스에 저장될 것입니다.

char형 배열 arr에 저장된 값을 인덱스 0부터 차례대로 검사하며 '(' 문자이면 카운트를 더해주고, ')' 문자이면 카운트를 감소시켜줍니다.

'(' 문자라면 단순히 카운트를 더해주면 되지만, ')'문자라면 검사해야 할 조건이 늘어납니다. 

VPS의 조건을 성립시키기 위해 만약 카운트가 0, 즉 ')' 문자와 상쇄되어야 할 '(' 문자가 없는 상태에서 ')' 문자가 한번 더 오게 되면 그 이후에는 '(' 문자나 ')' 문자에 관계없이 VPS 의 조건을 성립하지 않으므로 검사할 필요가 없습니다.

따라서 바로 break를 통해 검사하는 for문을 빠져나오게 되고, cnt는 -1의 값을 갖게 될 것입니다.  즉 cnt==0이라는 조건이 되지않아 NO 라는 문자열을 출력할 것입니다.

만약 VPS의 조건을 성립하여 ( 문자와 )문자가 제대로 상쇄되었다면 cnt==0 으로 결론이 나와서 YES라는 문자열을 출력해 줄 것입니다.

백준 알고리즘 - 2577번 숫자의 개수 문제입니다.

(참고 - https://www.acmicpc.net/problem/2577 )

코드 ) 

int main() {

int i, a, j, total=1;

int buf[10];

for(i = 0; i < 10; i++) {

buf[i] = 0;

}

for(i = 0; i < 3; i++) {

scanf("%d", &a);

total *= a;

}

for(i = 0; total > 0; i++) {

a = total % 10;

buf[a] += 1;

total /= 10;

}

for(i = 0; i < 10; i++) {

printf("%d\n", buf[i]);

}

}

- 먼저 for문을 통해 배열 buf를 0으로 초기화 해줍니다. (2563번에서 했듯이, 배열을 전역변수로 선언해도 0으로 자동 초기화할 수 있습니다.) 이 배열 buf는 0~10사이의 각각의 수에 대해 카운트하기 위해 사용될 것입니다.

그 후 3개의 수를 입력받아 total에 곱한 값을 누적하여 저장해줍니다.

total의 값이 0보다 큰 동안 반복합니다. total을 10으로 나눈 나머지의 값을 인덱스로 삼아 배열 buf의 a인덱스에 해당하는 위치에 1을 더해줍니다. total을 10으로 나눈 나머지가 a이므로, a는 0~9사이의 값이 될 수 밖에 없습니다.

그 후, total은 10을 나눠줍니다.

이렇게 계산한 뒤, 최종적으로 buf에 저장된 값들을 출력해주면 됩니다.