반응형
LinkedIn 개발자로 성장하면서 남긴 발자취들을 확인하실 수 있습니다.
Github WWDC Student Challenge 및 Cherish, Tiramisul 등 개발한 앱들의 코드를 확인하실 수 있습니다.
개인 앱 : Cherish 내 마음을 들여다보는 시간, 체리시는 디자이너와 PM과 함께 진행 중인 1인 개발 프로젝트입니다.
10년 후, 20년 후 나는 어떤 스토리 텔러가 되어 있을지 궁금하다. 내가 만약에 아직 조금 더 탐구하고 싶은 게 있고, 궁금한 게 있다면, 그게 설사 지금 당장의 내 인생에 도움이 안 되는 것 같더라도 경험해보자. 그 경험들을 온전히 즐기며 내 것으로 만들고, 내 일에 녹여내고... 그러다보면 그 점들이 모여 나란 사람을 그려내는 선이 될 테니까.

Recent Posts
Recent Comments
Total
관리 메뉴

꿈꾸는리버리

[백준 알고리즘] 2750 수 정렬하기 본문

오뚝이 개발자/알고리즘

[백준 알고리즘] 2750 수 정렬하기

rriver2 2021. 12. 6. 12:52
반응형

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

 

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

풀이방법:    

1) 버블 정렬

void bubblesort(int array[],int N){
    for(int i = 0; i < N-1; i++){
        for(int j = 0; j < N-1; j++){
            if(array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

 

2) 선택정렬

void selectsort(int array[],int N){
    for(int i = 0; i < N-1; i++){
        int min = i;
        for(int j = i+1; j < N; j++){
            if(array[min] >array[j]){
                min = j;
            }
        }
        if(i != min){
            int temp = array[min];
            array[min] = array[i];
            array[i] = temp;
        }
    }
}

 

3) 삽입정렬

void insertsort(int array[],int N){
    for(int i = 1; i < N; i++){
        int key = array[i];
        int j;
        for(j = i; j > 0 && array[j-1] > key; j--){
            array[j] = array[j-1];
        }
        array[j] = key;
        
        
    }
}

작성한 코드는 다음과 같다. 

#include <iostream>
using namespace std;

void bubblesort(int array[],int N){
    for(int i = 0; i < N-1; i++){
        for(int j = 0; j < N-1; j++){
            if(array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

void selectsort(int array[],int N){
    for(int i = 0; i < N-1; i++){
        int min = i;
        for(int j = i+1; j < N; j++){
            if(array[min] >array[j]){
                min = j;
            }
        }
        if(i != min){
            int temp = array[min];
            array[min] = array[i];
            array[i] = temp;
        }
    }
}

void insertsort(int array[],int N){
    for(int i = 1; i < N; i++){
        int key = array[i];
        int j;
        for(j = i; j > 0 && array[j-1] > key; j--){
            array[j] = array[j-1];
        }
        array[j] = key;
        
        
    }
}

int main() {
    int N;
    cin >> N;
    int array[N];
    for(int i = 0; i< N; i++){
        cin >> array[i];
    }
    //    셋 중 하나
    //    bubblesort(array,N);
    //    selectsort(array,N);
    insertsort(array,N);
    for(int i = 0; i< N; i++){
        cout<< array[i] <<"\n";
    }
    return 0;
}

 

성공한 사진!    

  MEMO 

버블 정렬을 주로 하다가 다른 정렬들을 다시 하니까 기억이 잘 안 났다.. 정렬 중에서는 삽입 정렬이 제일 어려운 것 같다.

 

오늘 알아본 정렬들의 시간복잡도

평균과 최악의 시간복잡도는 같지만 삽입 정렬의 경우 최선일 때 O(N)을 가진다.

why?

그 이유는 버블과 선택 정렬의 경우엔 12345 차례대로 되어있는 배열을 정렬하게 되더라도 전체 루프를 다 돌아야 하는 반면,

삽입 정렬의 경우에는 비교하는 인덱스의 앞 인덱스만 확인하기 때문이다.

예를 들어 삽입정렬에서 12345에서 5를 검사하고 있다고 하자.

그러면 4와 비교를 하고 5가 더 크니까 123과는 비교를 하지 않아도 된다.

반응형
저작자표시 비영리 변경금지

'오뚝이 개발자 > 알고리즘' 카테고리의 다른 글

[Swift][백준 알고리즘] 3085 사탕 게임  (0) 2022.04.15
[Swift][백준 알고리즘] 1107 리모컨  (0) 2022.04.13
[백준 알고리즘] 1436 영화감독 숌  (0) 2021.12.06
[백준 알고리즘] 1018 체스판 다시 칠하기  (0) 2021.12.06
[백준 알고리즘] 7568 덩치  (0) 2021.12.06
'오뚝이 개발자/알고리즘' Related Articles more
Comments