정렬 - 삽입정렬

삽입정렬

 

삽입정렬 이론

확실하게 짚고 넘어가야할 중요한 알고리즘이다. 

삽입정렬의 시간복잡도는 최선일 경우 O(N) , 최악일 경우 O(N*N)이 된다.

앞서 살펴봤던 이중 반복문으로 모든 곳을 탐색하여 최선과 최악일 경우의

시간 복잡도가 모두 O(N*N)이였던 선택정렬과 버블정렬에 비하면 낫긴 하지만

삽입정렬 역시 비효율적인 정렬 알고리즘에 속한다.

 

 

 

대략적인 코드를 작성해보면

 

int i, j;
    for(i=1; i<n; i++) {
        tmp = a[i];
        for(j=i-1; j>=0; j--) {
            if(a[j] > tmp) a[j+1] = a[j];
            else break;
        }
        a[j+1] = tmp;
    }

 

이렇게 나타낼 수 있다.

i가 1부터 돌고 j는 i-1에서 j=0까지 감소하는 for문을 돈다.

왼쪽의 수가 크면 오른쪽 수에 왼쪽 수를 넣고 그렇지 않은 경우(break) 되어

왼쪽의 비교되는 수의 오른쪽에 있는 a[j+1]에 tmp가 삽입된다.

 

 

삽입정렬 문제 1 : 단순 오름차순 정렬

문제 :
N개의 숫자 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 선택정렬입니다.
첫 번째 줄에 자연수 N(1<=N<=100) 주어지고, 두 번째 줄에 N개의 자연수가 공백 사이에 두고 입력된다.

입력예제 1
6
11 7 5 6 10 9

출력예제 1
5 6 7 9 10 11

소스코드 :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, nn, i, j, tmp;
    vector<int> v;
    cin >> n;
    for(i=0; i<n; i++) {
        cin >> nn;
        v.push_back(nn);
    }

    for(i=1; i<n; i++) {
        tmp = v[i];
        for(j=i-1; j>=0; j--) {
            if(v[j] > tmp) v[j+1] = v[j];
            else break;
        }
        v[j+1] = tmp;
    }
    
    for(i=0; i<n; i++) {
        cout << v[i] << " ";
    }
    
    return 0;
}

 

 

삽입정렬 문제 2 : 카카오 캐시 문제 변형

문제 :

캐리메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가

필요할 때 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.

철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다.

LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되징 않은 것 정도의 의미를 가지고 있다.

캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘이다.

 

만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로 저장되어 있다면,

(맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.)

 

1) Cache Miss : 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작업을 CPU가 사용한다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 5번 작업은 캐시의 맨 앞에 위치한다.

5 2 3 1 6

(7번 작업은 캐시에서 삭제한다.)

 

2) Cache Hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용한다면

Cache Hit가 되고, 3번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으로 위치하게 된다.

5 2 3 1 6  ---> 3 5 2 1 6

 

캐시의 크기가 주어지고, 캐시가 비어있는 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후

캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

 

입력설명 

첫 번째 줄에 캐시 크기인 S(3<=S<=10) , 작업의 개수 N(5<=N<=1,000) 입력된다.

두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~ 100 이다.

 

출력설명

마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.

소스코드 :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int s, n, t, i, j, pos;
    cin >> s >> n;
    vector<int> v(s,0);
    for(i=0; i<n; i++) {
        cin >> t;
        pos = -1;
        // Cache Hit인지 확인하고 Hit일 경우, pos에 j저장 
        for(j=0; j<s; j++) if(v[j] == t) pos=j;
        if(pos == -1) { // Cache Miss일 경우
            for(j=s-1; j>=1; j--) v[j] = v[j-1];
        }
        else { // Cache Hit일 경우 
            for(j=pos; j>=1; j--) v[j] = v[j-1];
        }
        v[j] = t; // v[0] = t;
        
        // 현재 캐시 메모리 상태 변화 출력
        for(int k=0; k<s; k++) {
            cout << v[k] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

 

실행결과 :

 

 

 

 

출처 (학습 자료) :

 

it 취업을 위한 알고리즘 문제풀이

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#curriculum