기초 정렬 알고리즘 문제 풀이

기초 정렬 알고리즘 문제 풀이

백준 온라인 저지 =  https://www.acmicpc.net/

 

문제 1

https://www.acmicpc.net/problem/2750

 

데이터의 개수가 1000개 이하이다. N^2을 하면 백만이다. 일반적으로 온라인 채점 시스템같은 경우는 1초에 1억번 정도 연산을 할 수 있다고 보면 된다. 즉, 백만개정도의 연산은 무리없이 가능하다.

 

#include <stdio.h>

 

//선택정렬

//데이터 개수가 1000개므로 1001개까지 배열을 만든다.

//이유는 배열의 인덱스가 0부터 시작하기 때문이다.

//즉, 인덱스를 0 ~ 1000까지 갖도록하게 하기 위함이다. 

int array[1001];

 

void show(int number){

           int i;

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

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

           }

}

 

int main(void){

           int number, i, j, min, index, temp;

           //데이터의 개수를 입력받는다.

           //&주소값에 데이터 저장.

           scanf("%d", &number);

           //5번 반복해서 데이터를 입력받는다.

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

                      scanf("%d", &array[i]);

           }

          

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

                      //절대값이 1000보다 작거나 같기때문에 1001로 설정한다.

                      //항상 들어오는 숫자보다 더 커야한다.  최소값으로 선택이 되기 위함이다.

                      min = 1001;

                      for(j = i; j < number; j++){

                                 //현재 요소가 최소값이라면

                                 if(min > array[j]){

                                             min = array[j];

                                             index = j;

                                 }

                      }

                      temp = array[i];

                      array[i] = array[index];

                      array[index] = temp;

           }

          

           show(number);

}

문제 2

https://www.acmicpc.net/problem/2752

문제 3

https://www.acmicpc.net/problem/2751

데이터 개수가 백만개 일때는 N * logN으로 풀어야 한다. 데이터 개수가 백만이면 log는 20이어서 시간복잡도는 2천만이된다. 이번 문제는 퀵정렬로 푼다. 퀵 정렬은 최악의 경우 시간복잡도가 N * N이 된다. C++ 라이브러리에서 제공해주는 sort함수를 사용하면 N * logN이 보장된다.

 

#include <stdio.h>

#include <algorithm>

 

int number, data[1000001];

 

void show(){

           for(int i = 0; i < number; i++){

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

           }

}

 

void quickSort(int * data, int start, int end){

           if (start >= end){

                      return;

           }

          

           int key = start;

           int i = start + 1, j = end, temp;

           while(i <= j){ //엇갈리지 않을 떄까지 반복

                      while(i <= end && data[i] <= data[key]){

                                 i++;

                      }

                     

                      while(j > start && data[j] >= data[key]){

                                 j--;

                      }

                     

                      if(i > j){

                                 temp = data[j];

                                 data[j] = data[key];

                                 data[key] = temp;

                      }else {

                                 temp = data[i];

                                 data[i] = data[j];

                                 data[j] = temp;

                      }

           }

          

           quickSort(data, start, j - 1);

           quickSort(data, j + 1, end);

}

 

int main(void){

           scanf("%d\n", &number);

           for(int i = 0; i < number; i++){

                      scanf("%d", &data[i]);

           }

           //퀵정렬은 최악의 경우 시간복잡도가 N * N이 나온다.

           //그래서 C++ 알고리즘 STL 라이브러리를 사용한다. N * logN을 보장한다.

           std::sort(data, data + number);

           //quickSort(data, 0, number - 1);

           show();

           return 0;

}