배열
배열은 메모리 상에 원소를 연속하게 배치한 자료구조이다. 원래 C++에서는 배열을 선언한 뒤에는 배열의 길이를 변경하는 것이 불가능하지만, 자료구조로써의 배열에서는 길이를 마음대로 늘이거나 줄일 수 있다고 생각하겠다.
배열의 성질
1. O(1)에 k번째 원소를 확인/변경 가능 - 배열은 메모리 상에 원소를 연속하게 배치한 자료구조라서 k번째 위치를 바로 계산할 수 있다.
2. 추가적으로 소모되는 메모리의 양(overhead)가 거의 없음
3. Cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림
배열의 연산
- 임의의 위치에 있는 원소를 확인하고 변경하는 연산 O(1)
- 원소를 끝에 추가하는 연산 O(1)
- 마지막 원소를 제거하는 연산 O(1)
- 임의의 위치에 원소를 추가, 삭제하는 연산 O(N) - 해당 위치에 존재하는 원소부터 뒤로 한 칸씩 밀거나 앞으로 한 칸씩 당겨야 해서 O(N)이 필요하다. 아래는 해당 코드이다.
#include <iostream>
using namespace std;
void insert(int idx, int num, int arr[], int& len) {
for (int i = len; i > idx; i--)
arr[i] = arr[i - 1];
arr[idx] = num;
len++;
}
void erase(int idx, int arr[], int& len) {
len--;
for (int i = idx; i < len; i++)
arr[i] = arr[i + 1];
}
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();
}
배열 전체를 특정 값으로 초기화시킬 때 어떻게 하면 효율적일까.
1. memset 함수 - 실수할 여지가 굉장히 많아서 비추천
2. for 문을 돌며 값을 하나하나 다 바꾼다. - 투박하긴 하지만 실수할 여지 없어서 무난하니 좋다.
3. algorithm 헤더의 fill함수 사용 - fill함수는 실수할 여지도 없고 코드도 짧아 익숙해지면 가장 추천.
#include <string.h>
#include <algorithm>
using namespace std;
int a[21];
int b[21][21];
int main() {
//1.memset
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
//2. for
for (int i = 0; i < 21; i++)
a[i] = 0;
for (int i = 0; i < 21; i++)
for (int j = 0; j < 21; j++)
b[i][j] = 0;
//3. fill
fill(a, a + 21, 0);
for (int i = 0; i < 21; i++)
fill(b[i], b[i] + 21, 0);
}STL vector
vector는 배열과 거의 동일한 기능을 수행하는 자료 구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱스를 가지고 각 원소로 접근할 수이다. 그런데 vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있다.
그래프의 인접 리스트를 저장할 때에는 vector를 쓰는게 많이 편해서 vector가 필요하게 되지만 그전까지는 굳이 배열 대신 vector를 써야 하는 상황이 딱히 없다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
vector<int> v1(3, 5); // {5,5,5};
cout << v1.size() << '\n'; // 3
v1.push_back(7); // {5,5,5,7};
vector<int> v2(2); // {0,0};
v2.insert(v2.begin()+1, 3); // {0,3,0};
vector<int> v3 = {1,2,3,4}; // {1,2,3,4}
v3.erase(v3.begin()+2); // {1,2,4};
vector<int> v4; // {}
v4 = v3; // {1,2,4}
cout << v4[0] << v4[1] << v4[2] << '\n';
v4.pop_back(); // {1,2}
v4.clear(); // {}
}insert와 erase가 이미 메소드로 구현이 되어있다. 앞서 배열에서 살펴본 바와 같이 시간 복잡도는 O(N)이다. push_back, pop_back은 제일 끝에 원소를 추가하거나 빼는 것이니 O(1)이다.
vector에서 =를 사용하면 deep copy가 발생한다. 16번째 줄 v4=v3에서 v4는 {1,2,4}가 되었고 이후 v4를 바꿔도 v3에는 영향을 주지 않는다.
- vector에 있는 모든 원소 순회
vector<int> v1={1,2,3,4,5,6};
//1. range-based for loop(c++11 이후로)
for(int e:v1)
cout<<e<<' ';
//2. for 사용- 나쁘지 않음
for(int i=0;i<v1.size();i++)
cout<<v1[i]<<' ';
//3.잘못된 방법
for(int i=0;i<=v1.size()-1;i++)
cout<<v1[i]<<' ';range-based for loop는 e에 v1원소들이 하나씩 들어가는 for문이 된다.
지금은 값을 바꾸지 않고 출력만 해서 상관없지만 만약 int e : v1이라고 하면 복사된 값이 e에 들어가고 int& e : v1이라고 하면 원본이 e에 들어간다.
그래서 int e:v1이라고 쓴 for문 내에서 e를 바꿔도 v1에는 영향이 가지 않지만 int&e:v1이라고 쓴 for문 내에서는 e를 바꾸면 v1에서 실제 해당 원소의 값이 바뀌게 된다.
이 기능은 vector 뿐 아니라 list, map, set등에서도 모두 사용 가능하므로 기억해두면 좋다. 하지만 c++11부터 추가된 기능이므로 코딩 테스트가 c++11을 지원하지 않는다면 사용할 수 없다.
만약 range-based for loop가 그다지 익숙하지 않다면 for문으로 인덱스르 하나씩 다 돌아도 된다.
하지만 3번과 같이 쓰면 잘못될 수 있다.
그 이유는 vetor의 size메소드는 시스템에 따라 unsigned int 혹은 unsigned long long을 반환한다.
그렇기 때문에 32비트 컴퓨터 기준 3번같이 쓰면 v1이 빈 vector일 때 v1.size()-1이 unsigned int 0에서 int 1을 빼는 식이 되고, unsigned int와 int를 연산하면 unsigned int로 자동 형 변환이 발생하기 때문에 (unsigned int) 0-(int) 1은 -1이 아니라 4294977295가 되어버린다.
이 값은 unsigned int overflow로 인해 생기게 된 값이다.
따라서 v1[0], v1 [1], v1 [2],... 이렇게 i가 계속 커지다가 어느 순간 런타임 에러가 발생하게 될 것이다.
=> vector에서 모든 원소 순회는 range based for loop를 사용해도 되고 for문으로 인덱스를 하나씩 다 돌아도 된다.
하지만 size 메소드의 반환 값이 unsigned이기 때문에 3번처럼 구현하면 안 된다.