졍's 기술 블로그

백준 사이트

초심자라면 단계별로 풀어보기, 알고리즘 분류에서 문제 풀어보는 게 좋다.

그 중에서도 단계별로 풀어보기에서 정렬해보기부터 시작하면 좋다.

기본적으로 1초에 1억 번 정도 연산한다고 생각하고 문제 풀면 됨.

1. 수 정렬하기(2750)

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

데이터의 개수가 최대 1,000개. N^2 = 1,000,000개

N^2 알고리즘으로 풀어도 크게 문제 없이 해결 가능하다.

#include <iostream>
using namespace std;

void Print(int *data, int N){
    for(int i=0;i<N;i++)
        cout << data[i] << endl;
}

void Selection_Sort(int *data, int N){
    int tmp, min, idx = 0;
    for(int i=0;i<N;i++){
        min = 1001;
        for(int j=i;j<N;j++){
            if(min > data[j]){
                min = data[j];
                idx = j;
            }
        }

        tmp = data[i];
        data[i] = data[idx];
        data[idx] = tmp;
    }
}

void Bubble_Sort(int *data, int N){
    int tmp = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(data[j] > data[j+1]){
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}

int main(void){
    int N;
    int data[1000];

    cin >> N;
    for(int i=0;i<N;i++)
        cin >> data[i];

    Selection_Sort(data, N);
    Bubble_Sort(data, N);
    //Insert_Sort(data, N);
    //Quick_Sort(data, N);
    Print(data, N);
    return 0;
}

2. 세수정렬

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

#include <iostream>
using namespace std;
#define N 3

int arr[3]={0,};

void Input(){
    for(int i=0;i<N;i++)
        cin >> arr[i];
}

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << " ";
}

void Insertion_Sort(){
    int j, tmp;
    for(int i=0;i<N-1;i++){
        j = i;
        while(arr[j] > arr[j+1]){
            tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            j--;
        }
    }
}

int main(void){

    Input();
    //Selection_Sort();
    Insertion_Sort();
    Output();

    return 0;
}

3. 수 정렬하기 2

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

#include <iostream>
using namespace std;

int N;
int arr[1000000+10];

void Input(){
    cin >> N;
    for(int i=0;i<N;i++)
        cin >> arr[i];
}

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << "\n";
}

void Quick_Sort(int start, int end){
    
    if(start >= end)
        return;

    int mid = start;
    int i = start+1;
    int j = end;
    int tmp;

    while(i <= j){
        // 오른쪽으로 가면서 pivot값보다 큰 값 찾기
        while(arr[mid] >= arr[i]){
            i++;
        }

        // 왼쪽으로 가면서 pivot값보다 작은 값 찾기
        while(arr[mid] <= arr[j] && start < j){
            j--;
        }

        // 엇갈렸으면 pivot 값과 작은 값 변경
        if(i > j){
            tmp = arr[j];
            arr[j] = arr[mid];
            arr[mid] = tmp;
        }
        // 엇갈리지 않았으면 두 값 변경
        else{
            tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = arr[j];
        }
    }

    // start, end 다시 조정해 재귀
    Quick_Sort(start, j-1);
    Quick_Sort(j+1, end);
}

int main(void){
    Input();
    Quick_Sort(0, N-1);
    Output();
}

버블 정렬(Bubble Sort)

: 옆에 있는 값과 비교해 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법

버블 정렬 Sequence

더보기

한 번 반복이 끝났을 때 가장 큰 값이 가장 마지막 위치로 이동

코드

#include <iostream>
using namespace std;

int main(void){
    int i, j, tmp;
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        for(j=0;j<9-i;j++){ // i for문이 1번 반복될 때마다 가장 마지막 위치의 원소는 채워지기 때문에 idx 9-i까지만 확인
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }

    for(i=0;i<10;i++){
        cout << arr[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 1) / 2

= N * (N - 1) / 2

= O(N^2)

실제로 실행시켜보면 Bubble Sort가 Selection Sort보다 더 느리게 작동한다.
: Bubble Sort는 당장 옆에 있는 것과 비교해 자리를 바꾸는 연산을 수행하며, 자리를 바꾸는 연산은 총 3번의 연산을 필요로 하기 때문에 컴퓨터가 실질적으로 수행해야하는 명령어가 더 많기 때문이다.
반면에 선택 정렬은 가장 작은 수를 찾아 마지막에 한 번만 자리를 바꾸는 연산을 수행한다.

참고로, 정렬 알고리즘 중 가장 느린 건 Bubble Sort이다.

선택 정렬(Selection sort)

: 가장 작은 것을 선택해서 가장 앞으로 보내는 알고리즘

코드

#include <iostream>
using namespace std;

int main(void){
    // 선택 정렬: 가장 작은 것을 선택해서 가장 앞으로 보내자
    int i, j, min, idx, tmp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        min = 9999;
        for(j=i;j<10;j++){
            if(min > array[j]){
                min = array[j];
                idx = j;
            }
        }
        tmp = array[i];
        array[i] = array[idx];
        array[idx] = tmp;
        cout << array[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 9) / 2

=> N * (N - 1) / 2

∴ O(N^2)