배열
배열은 메모리 상에 원소를 연속하게 배치한 자료구조이다.
배열의 성질
- K번째 원소의 위치를 바로 알 수 있다. 즉, K번째 원소는 O(1) 시간복잡도를 가진다.
- 추가적으로 소모되는 메모리의 양(overhead)이 거의 없다.
- Cache hit rate가 높다.
- 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다.
Cache hit ratio
캐시는 컴퓨터 과학에서 데이터나 값을 미리 복사해놓는 임시 장소를 의미한다.
캐시 적중률은 데이터가 캐시에 존재하는 경우 히트(캐시가 저장된 데이터나 콘텐츠를 표시할 수 있는 경우)
존재하지 않는 경우는 캐시 미스(캐시 메모리에 저장되어 있지 않을 때)
배열 임의의 위치에 있는 원소를 확인, 변경
시간 복잡도 : O(1)
배열 마지막에 원소를 추가
시간 복잡도 : O(1)
배열 마지막 원소를 제거
시간 복잡도 : O(1)
배열 임의의 위치에 원소를 추가
시간 복잡도 : O(N)
임의의 위치에 원소를 추가할 때는 O(N)만큼의 시간 복잡도를 가진다. 밀어야 할 원소가 많을 수록 시간 복잡도가 늘어나고 적을 수록 줄어들지만 평균적으로 N/2 개를 밀어야 하므로 시간 복잡도를 O(N)으로 봐도 무방하다.
배열 임의의 위치 원소를 제거
시간 복잡도 : O(N)
추가하는 것과 마찬가지로 임의의 위치 원소를 제거할 때도 O(N)만큼의 시간 복잡도를 가진다.
k번째 원소를 지우는 경우 그 이후에 있는 원소를 모두 한 칸씩 이동시켜야 하므로 O(N)
실습
바킹독님의 실습 코드를 받아온 후 배열의 임의의 위치에 원소를 추가, 제거하는 코드를 작성해보았다.
insert와 erase 함수 부분에 코드를 작성하면 된다.
#include <bits/stdc++.h>
using namespace std;
void insert(int idx, int num, int arr[], int& len){
/* 코드 작성 부분 */
len++;
for(int i = len; i > idx; i--){
arr[i] = arr[i - 1];
}
arr[idx] = num;
}
void erase(int idx, int arr[], int& len){
/* 코드 작성 부분 */
for(int i = idx; i < len; i++){
arr[i] = arr[i + 1];
}
len--;
}
void printArr(int arr[], int& len){
for(int i = 0; i < len; i++) cout << arr[i] << ' ';
cout << "\n\n";
}
void insert_test(){
cout << "***** insert_test *****\n";
int arr[10] = {10, 20, 30};
int len = 3;
insert(3, 40, arr, len); // 10 20 30 40
printArr(arr, len);
insert(1, 50, arr, len); // 10 50 20 30 40
printArr(arr, len);
insert(0, 15, arr, len); // 15 10 50 20 30 40
printArr(arr, len);
}
void erase_test(){
cout << "***** erase_test *****\n";
int arr[10] = {10, 50, 40, 30, 70, 20};
int len = 6;
erase(4, arr, len); // 10 50 40 30 20
printArr(arr, len);
erase(1, arr, len); // 10 40 30 20
printArr(arr, len);
erase(3, arr, len); // 10 40 30
printArr(arr, len);
}
int main(void) {
insert_test();
erase_test();
}처음 짜봐서 생각보다 어려웠다.
결국 해설 코드 보면서 코드를 이해하려고 했다..ㅠㅠ
해설
insert 함수의 경우 원소를 맨 오른쪽 끝부터 1개씩 이동하면서 이동시키면 된다.
여기서 for문의 조건 작성할 때 >= 와 같이 작성하는 경우 0번째 자리에 원소를 추가한다고 할 때 -1 번째 인덱스를 사용하게 되어 런타임 에러가 발생할 수 있으므로 인덱스를 잘 작성하는 것이 좋다.
erase 함수는 왼쪽부터 처리하면 추가적인 메모리를 사용하지 않고 해결할 수 있다.
배열 전체를 특정 값으로 초기화 시키는 팁
- cstring 헤더에 있는 memset함수를 활용하는 방법
단, memset 함수는 실수할 여지가 있다. 예를 들어 0이나 -1 이 아닌 다른 값을 넣으면 오동작 하거나, 2차원 이상의 배열을 함수 인자로 넘긴 후 그곳에서 memset을 하면 잘못 들어간다거나 하는 등의 문제가 생길 수 있으므로 추천하지 않는 방식.
- 반복문으로 값을 하나씩 다 바꾸는 방법
실수할 여지 없이 무난하다.
- algorithm 헤더의 fill 함수 이용하는 방법
fill 함수는 실수할 여지도 없고 코드가 짧아서 가장 추천하는 방법
참고자료
[바킹독의 실전 알고리즘] 0x03강 - 배열
위키백과 캐시
캐시 적중률
What are Hit and Miss Ratios?
