[Baekjoon] - 12단계 : 정렬

July 29, 2021

1. 수 정렬하기

#include <stdio.h>

void sort(int *arr, int start, int end){
    
    if(start>=end){//엇갈리면
        return;
    }
    
    int pivot = start;    //피봇
    int i = pivot+1;    //i는 피봇 다음원소
    int j = end;    //j는 마지막 원소
    int temp;
    
    while(i<=j){//i가 더 커지면 종료
        //피봇 보다 큰 값 만날 때 까지
        while(i<=end && arr[i]<=arr[pivot]){
            ++i;
        }
        //피봇 보다 작은 값 만날 때 까지
        while(j>start && arr[j]>=arr[pivot]){
            --j;
        }
        
        //위에서 계산된 i와 j가 만나거나 엇갈리면 종료
        if(i>=j) break;
        
        //두 원소 교환
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    //피봇 정렬 완료
    temp = arr[j];
    arr[j] = arr[pivot];
    arr[pivot] = temp;
    
    sort(arr, start, j-1);    //피봇 중심으로 왼쪽부분 분할
    sort(arr, j+1, end);    //피봇 중심으로 오른쪽부분 분할
}

int main(){
    
    int t;
    scanf("%d",&t);
    
    int arr[1001];
    for(int i=0;i<t;i++) scanf("%d",&arr[i]);
    
    sort(arr, 0, t-1);
    
    //출력
    for(int i=0;i<t;++i){
        printf("%d ", arr[i]);
    }
    
    return 0;
}

2. 수 정렬하기 2

# include <stdio.h>
# define MAX_SIZE 1000001
int sorted[MAX_SIZE];// 추가적인 공간이 필요

// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){
    if(list[i]<=list[j])
      sorted[k++] = list[i++];
    else
      sorted[k++] = list[j++];
  }

  // 남아 있는 값들을 일괄 복사
  if(i>mid){
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];
  }
  // 남아 있는 값들을 일괄 복사
  else{
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(int list[], int left, int right){
  int mid;

  if(left<right){
      mid = (left+right)/2; // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
    merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
    merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
  }
}

int main(){
    int t;
    scanf("%d",&t);
    int list[MAX_SIZE];
    for(int i=0;i<t;i++) scanf("%d", &list[i]);
  // 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
  merge_sort(list, 0, t-1);

  // 정렬 결과 출력
  for(int i=0; i<t; i++){
    printf("%d\n", list[i]);
  }
}

3. 수 정렬하기 3

#include <stdio.h>

int main(){
    int t;
    scanf("%d",&t);
    
    int num[10001] = {0,};
    
    int n;
    for(int i=0;i<t;i++){
        scanf("%d",&n);
        num[n]++;
    }
    for(int i=1;i<10001;i++){
        if(num[i] == 0) continue;
        else{
            for(int j=0;j<num[i];j++) printf("%d\n",i);
        }
    }
}

4. 통계학

# include <stdio.h>
# define MAX_SIZE 500001
int sorted[MAX_SIZE];// 정렬된 값 담을 배열

// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스

void merge(double list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;//정렬될 인덱스

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){//왼쪽배열,오른쪽배열 인덱스들이 각 배열을 벗어나지 않을 경우
    if(list[i]<=list[j])//인덱스 i값이 작으면
      sorted[k++] = list[i++];
    else
      sorted[k++] = list[j++];
  }

  if(i>mid){//왼쪽배열 인덱스가 왼쪽배열 벗어날 경우
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];//오른쪽배열 남은 값 복사
  }
  else{//오른쪽배열 인덱스가 오른쪽배열 벗어날 경우
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];//왼쪽배열 남은 값 복사
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(double list[], int left, int right){
  int mid;

  if(left<right){
      mid = (left+right)/2; // 중간 위치를 계산
      
    merge_sort(list, left, mid); // 앞쪽 부분 나누기
    merge_sort(list, mid+1, right); // 뒤쪽 부분 나누기
      
    merge(list, left, mid, right);//정렬 후 배열 합하기
  }
}

int main(){
    int n;
    scanf("%d",&n);
    
    int sum = 0;
    double num[500001];
    for(int i=0;i<n;i++){//합하기
        scanf("%lf",&num[i]);
        sum += num[i];
    }
    
    merge_sort(num, 0, n-1);
    
    int arr[8001]={0,};
    for(int i=0;i<n;i++){
        arr[(int)num[i]+4000]++;
    }
    
    int max = 0;
    for(int i=0;i<n;i++){//빈도수 최대치 구하기
        if(arr[(int)num[i]+4000] == 0) continue;
        max = max < arr[(int)num[i]+4000] ? arr[(int)num[i]+4000] : max;
    }
    
    int list[8001]={0,};
    int index = 0;
    int pre = 50000;
    for(int i=0;i<n;i++){//최대빈도인 값들만 list에 담기
        if(arr[(int)num[i]+4000] == max){
            if(pre != (int)num[i]){
                list[index++] = (int)num[i];
                pre = (int)num[i];
            }
        }
    }
    
    double a = sum/(double)n;
    int b = num[n/2];
    
    int c;
    if(index > 1) c = list[1];//최대빈도 값이 여러개면 두번째 값
    else c = list[0];
    
    int d = num[n-1] - num[0];
    
    printf("%.lf %d %d %d",a,b,c,d);
}

5. 소트인사이드

#include <stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    
    int arr[10]={0,};
    
    while(n > 0){
        arr[n%10]++;
        n /= 10;
    }
    for(int i=9;i>=0;i--){
        for(int j=0;j<arr[i];j++){
            printf("%d",i);
        }
    }
}

6. 좌표 정렬하기

# include <stdio.h>
# define MAX_SIZE 100001

struct point{
    int x;
    int y;
};

struct point sorted[MAX_SIZE];

void merge(struct point list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;//정렬될 인덱스

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){//왼쪽배열,오른쪽배열 인덱스들이 각 배열을 벗어나지 않을 경우
    if(list[i].x < list[j].x)//인덱스 i값이 작으면
      sorted[k++] = list[i++];
    else if(list[i].x > list[j].x)
      sorted[k++] = list[j++];
    else{
        if(list[i].y <= list[j].y)
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
  }

  if(i>mid){//왼쪽배열 인덱스가 왼쪽배열 벗어날 경우
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];//오른쪽배열 남은 값 복사
  }
  else{//오른쪽배열 인덱스가 오른쪽배열 벗어날 경우
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];//왼쪽배열 남은 값 복사
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(struct point list[], int left, int right){
  int mid;

  if(left<right){
      mid = (left+right)/2; // 중간 위치를 계산
      
    merge_sort(list, left, mid); // 앞쪽 부분 나누기
    merge_sort(list, mid+1, right); // 뒤쪽 부분 나누기
      
    merge(list, left, mid, right);//정렬 후 배열 합하기
  }
}

int main(){
    int t;
    scanf("%d",&t);
    
    struct point list[MAX_SIZE];
    for(int i=0;i<t;i++) scanf("%d %d", &list[i].x, &list[i].y);
  
    merge_sort(list, 0, t-1);

    for(int i=0; i<t; i++){//출력
        printf("%d %d\n", list[i].x ,list[i].y);
    }
}

7. 좌표 정렬하기 2

# include <stdio.h>
# define MAX_SIZE 100001

struct point{
    int x;
    int y;
};

struct point sorted[MAX_SIZE];

void merge(struct point list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;//정렬될 인덱스

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){//왼쪽배열,오른쪽배열 인덱스들이 각 배열을 벗어나지 않을 경우
    if(list[i].y < list[j].y)//인덱스 i값이 작으면
      sorted[k++] = list[i++];
    else if(list[i].y > list[j].y)
      sorted[k++] = list[j++];
    else{
        if(list[i].x <= list[j].x)
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
  }

  if(i>mid){//왼쪽배열 인덱스가 왼쪽배열 벗어날 경우
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];//오른쪽배열 남은 값 복사
  }
  else{//오른쪽배열 인덱스가 오른쪽배열 벗어날 경우
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];//왼쪽배열 남은 값 복사
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(struct point list[], int left, int right){
  int mid;

  if(left<right){
      mid = (left+right)/2; // 중간 위치를 계산
      
    merge_sort(list, left, mid); // 앞쪽 부분 나누기
    merge_sort(list, mid+1, right); // 뒤쪽 부분 나누기
      
    merge(list, left, mid, right);//정렬 후 배열 합하기
  }
}

int main(){
    int t;
    scanf("%d",&t);
    
    struct point list[MAX_SIZE];
    for(int i=0;i<t;i++) scanf("%d %d", &list[i].x, &list[i].y);
  
    merge_sort(list, 0, t-1);

    for(int i=0; i<t; i++){//출력
        printf("%d %d\n", list[i].x ,list[i].y);
    }
}

8. 단어 정렬

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

typedef struct {
    char string[51];
    int length;
} str;

str sort[20001];

void merge(str* arr, int first, int mid, int last) {
    int i = first;
    int j = mid + 1;
    int k = first;

    while(i <= mid && j <= last) {
        if (arr[i].length < arr[j].length) {
            sort[k++] = arr[i++];
        } else if (arr[i].length > arr[j].length) {
            sort[k++] = arr[j++];
        } else {
            if (strcmp(arr[i].string, arr[j].string) < 0) {
                sort[k++] = arr[i++];
            }
            else {
                sort[k++] = arr[j++];
            }
        }
    }
    if (i > mid) {
        while (j <= last)
            sort[k++] = arr[j++];
    }
    else {
        while (i <= mid)
            sort[k++] = arr[i++];
    }
    for (k = first; k <= last; k++) 
        arr[k] = sort[k];
}

void mergesort(str* arr, int first, int last) {
    int mid;
    if (first < last) {
        mid = (first + last) / 2;
        mergesort(arr, first, mid);
        mergesort(arr, mid + 1, last);
        merge(arr, first, mid, last);
    }
}

int main(void)
{
    int N;
    scanf("%d", &N);
    str arr[N];

    for(int i = 0; i < N; i++) {
        scanf("%s", arr[i].string);
        arr[i].length = strlen(arr[i].string);
    }

    mergesort(arr, 0, N - 1);

    printf("%s\n", arr[0].string);
    for (int i = 1; i < N; i++) {
        if (strcmp(arr[i-1].string, arr[i].string) != 0)
            printf("%s\n", arr[i].string);
    }
    return 0;
}

9. 나이순 정렬

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

typedef struct {
    char string[101];
    int age;
    int index;
} str;

str sort[100001];

void merge(str* arr, int first, int mid, int last) {
    int i = first;
    int j = mid + 1;
    int k = first;

    while(i <= mid && j <= last) {
        if (arr[i].age < arr[j].age) {
            sort[k++] = arr[i++];
        } else if (arr[i].age > arr[j].age) {
            sort[k++] = arr[j++];
        } else {
            if (arr[i].index < arr[j].index) {
                sort[k++] = arr[i++];
            }
            else sort[k++] = arr[j++];
        }
    }
    if (i > mid) {
        while (j <= last)
            sort[k++] = arr[j++];
    }
    else {
        while (i <= mid)
            sort[k++] = arr[i++];
    }
    for (k = first; k <= last; k++)
        arr[k] = sort[k];
}

void merge_sort(str* arr, int first, int last) {
    int mid;
    if (first < last) {
        mid = (first + last) / 2;
        merge_sort(arr, first, mid);
        merge_sort(arr, mid + 1, last);
        merge(arr, first, mid, last);
    }
}

int main(void)
{
    int N;
    scanf("%d", &N);
    str arr[100001];

    int k = 0;
    for(int i = 0; i < N; i++) {
        scanf("%d %s", &arr[i].age , arr[i].string);
        arr[i].index = k++;
    }

    merge_sort(arr, 0, N - 1);

    for (int i = 0; i < N; i++) {
        printf("%d %s\n", arr[i].age,arr[i].string);
    }
    return 0;
}

요약

1번은 퀵정렬
2번은 병합정렬
4번은 퀵정렬로 시간초과 나온다.
5번에 초기화를 꼮 하자.
6번은 구조체를 써줌.7번은 xy만 바꾼조건이다.
c언어는 초기화 잘해주고 배열범위할당 잘해줘야한다.

Twitter Facebook LinkedIn

칸비

[Baekjoon] - 12단계 : 정렬

1. 수 정렬하기

2. 수 정렬하기 2

3. 수 정렬하기 3

4. 통계학

5. 소트인사이드

6. 좌표 정렬하기

7. 좌표 정렬하기 2

8. 단어 정렬

9. 나이순 정렬

요약

공유하기

참고

[STL] - map

[STL] - string

[Unity] - 선형보간 (Lerp)

[Unity] - 코루틴 (Coroutine) (2)