[BaekJoon/백준] 2751번

이 문제를 풀기까지의 여행은 10월 5일로 거슬러올라간다...

소트 문제들이 서서히 나오는걸보고, 아 공부좀 해야겠다 싶어서 '자료구조와 알고리즘' 도서를 구입해 공부했고

현재 정렬단원을 마무리해서, 이제 다시 백준을 풀어본다!!!!!!

 

총 3가지로 풀었다.

 

1. Merge_Sort (병합 정렬) Feat. 배열 공유방식

#include <stdio.h>
#include <stdlib.h>

static int *buff;

void __merge_sort(int a[], int left, int right) {
    if(left < right) {
        int p = 0;
        int i;
        int j = 0;
        int k = left;
        int center = (left + right) / 2;
        
        __merge_sort(a, left, center);
        __merge_sort(a, center+1, right);
        
        for(i = left; i <= center; i++) {
            buff[p++] = a[i];
        }
        
        while(i <= right && j < p) {
            a[k++] = (buff[j] <= a[i])?buff[j++]:a[i++];
        }
        
        while(j < p) {
            a[k++] = buff[j++];
        }
    }
}

int merge_sort(int a[], int n) {
    if((buff=calloc(n, sizeof(int))) == NULL)
       return -1;
    __merge_sort(a, 0, n - 1);
    free(buff);
    return 0;
}

int main() {
    int i, nx;
    int *x;
    scanf("%d", &nx);
    
    x = calloc(nx, sizeof(int));
    
    for(i = 0; i < nx; i++)
        scanf("%d", &x[i]);
    
    merge_sort(x, nx);
    
    for(i = 0; i < nx; i++)
        printf("%d\n", x[i]);
 
    free(x);
    
    return 0;
}

2. Merge_Sort (병합정렬) Feat. 배열공유 x 방식 (직관적)

#include <stdio.h>
#include <stdlib.h>

void merge_sort(int a[], int n, int c[]) {
    
    int mid = (n - 1) / 2;
    
    if(n >= 2) {
        merge_sort(a, mid + 1, c);
        merge_sort(a + mid + 1, n -(mid + 1), c);
                
        int pa = 0, pb = mid + 1, pc = 0;
        
        while(pa <= mid && pb <= n - 1) {
            a[pa] <= a[pb] ? (c[pc++]=a[pa++]):(c[pc++]=a[pb++]);
        }
        while(pa<=mid)
            c[pc++] = a[pa++];
        while(pb<=n-1)
            c[pc++] = a[pb++];
        
        for(int x = 0; x < n ; x++) {
            a[x] = c[x];
        }
    }
}

int main() {
    int i, nx;
    int *x, *b;
    scanf("%d", &nx);
    
    x = calloc(nx, sizeof(int));
    b = calloc(nx, sizeof(int));

    
    for(i = 0; i < nx; i++)
        scanf("%d", &x[i]);
    
    merge_sort(x, nx, b);
    
    for(i = 0; i < nx; i++)
        printf("%d\n", x[i]);
 
    free(x);
    free(b);
    
    return 0;
}

3. Heap_Sort (힙정렬)

#include <stdio.h>
#include <stdlib.h>

#define swap(type, x, y) do { type t = x; x = y; y = t;} while(0)

static void downheap (int a[], int left, int right) {
    int temp = a[left];
    int child;
    int parent;
    
    
    for(parent = left; parent < (right + 1) / 2; parent = child) {
        int cl = parent * 2 + 1;
        int cr = cl + 1;
        
        child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
        
        if(temp >= a[child])
            break;
        
        a[parent] = a[child];
    }
    a[parent] = temp;
}

void heap_sort(int a[], int n) {
    int i;
    
    for(i = (n - 2) / 2; i >= 0; i--) {
        downheap(a, i, n - 1);
    }
    for(i = n - 1; i > 0; i--) {
        swap(int, a[0], a[i]);
        downheap(a, 0, i - 1);
    }
}

int main(void) {
    int i, nx;
    int *x;
    scanf("%d", &nx);
    x = calloc(nx, sizeof(int));
    
    for(i = 0; i < nx; i++) {
        scanf("%d", &x[i]);
    }
    
    heap_sort(x, nx);
    for(i = 0; i < nx; i++) {
        printf("%d\n", x[i]);
    }
    
    free(x);
    
    return 0;
}

 

기분좋다아~ 공부하던 책의 오류도 찾았다 ㅋㅋ