< 배열 >
< 배열의 성질 >
-
시간복잡도 O(1)에 k번째 원소를 확인 및 변경 가능
-
임의의 위치 원소 추가 = O(n) <- 한 칸씩 뒤로 밀어야 한다
-
임의의 위치 원소 제거 = O(n) <- 한 칸씩 당겨온다
-
원소를 끝에 추가 = O(1)
-
마지막 원소 제거 = O(1)
-
추가적으로 소모되는 메모리의 양(= overhead)가 거의 없음
-
Cache hit rate가 높음
-
메모리 상에 연속한 구간을 잡아야 하므로 할당에 제약이 있다
< 사용 팁 >
- 배열 초기화
- 안전하게 for문을 통해 하나씩 할당
- algorithm 헤더의 fill 사용
#include <bits/stdc++.h>
using namespace std;
int main(void){
int a[10];
fill(a, a + 10, 0);
int b[10] = { 0, };
for (int i = 0; i < 10; i++)
printf("%d ", a[i]);
printf("\n");
for (int i = 0; i < 10; i++)
printf("%d ", b[i]);
return 0;
}
// 기존 c 스타일과 fill을 사용해서 배열을 초기화했다
위 결과 동일하게 배열 a,b 모두 0으로 초기화되었다
int a[10];
fill(a, a + 10, 3);
int b[10] = { 2, };위와 같이 수정한 경우에는 어떻게 될까???
사진처럼 fill의 경우에는 모든 원소가 정상적으로 초기화 되었지만, 0이 아닌 경우 b는 첫 원소만 해당값으로 초기화되고 나머지는 0값을 가지게 된다
fill을 통해 편하게 초기화 가능!!!
< STL 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}; = O(1)
// 변수로 크기 설정 가능 !!
int size = 10;
vector<int> v10(size, 3);
cout << v10.size(); // = 10
// insert, erase = O(N)
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} = O(1)
v4.clear(); // {}
}
// 제일 앞의 원소를 빼거나 추가하는
// pop_front, push_front 메소드는 O(N) !!!
위 코드에서 v4 = v3 부분에서는 deep copy가 일어난다
따라서 v4가 변경되어도 v3에는 영향을 주지 않는다!!!
vector에서 = 사용 시 >>> deep copy!!
< vector 순회 >
#include <bits/stdc++.h>
using namespace std;
int main(void){
vector<int> v = { 1,2,3,4,5,6 };
printf("%d\n", v.size());
printf("%lld\n", v.size() - 1);
printf("\n");
// 1. range-based for loop (c++ 11부터 사용 가능)
for (int e : v)
printf("%d ", e);
printf("\n");
// 2. index로 반복
for (int i = 0; i < v.size(); i++)
printf("%d ", v[i]);
printf("\n");
//3. 2번 방식 사용 시 주의!! (잘못된 방법)
for (int i = 0; i <= v.size()-1; i++)
printf("%d ", v[i]);
return 0;
}(중요!) vector.size() 는 unsigned int를 반환한다
따라서 3번의 방식에서 v가 빈 벡터인 경우 unsigned int 0에서 int1을 빼게 된다
unsigned int - int의 경우 답이 unsigned int로 자동 형변환이 되므로 -1 이 아닌 4294967295라는 값이 나온다
권장문제
매 순간 최선을 다하자