정렬 - 삽입정렬
삽입정렬
삽입정렬 이론
확실하게 짚고 넘어가야할 중요한 알고리즘이다.
삽입정렬의 시간복잡도는 최선일 경우 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