목차
0x00 배열의 정의와 성질
0x01 기능과 구현
0x02 STL vector
0x03 연습문제
0x00 배열의 정의와 성질
정의
메모리 상에 원소를 연속하게 배치한 자료구조
성질
1. O(1)에 k번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리의 양(overhead)이 거의 없음
3. Cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림
참고) Cache hit rate 가 높다는 의미
캐시 적중률이 높다 == 캐시를 참조했더니 데이터가 존재하는 확률이 높다.
캐시의 지역성에 기반하여 캐시에 존재하는 데이터의 주변 데이터도 곧 사용할 가능성이 높은 데이터다.
배열은 메모리상에 연속한 구간에 존재하기 때문에 Cache hit rate가 높다.
0x01 기능과 구현
조회, 수정 O(1)
인덱스로 바로 접근할 수 있으니까 O(1) 시간이 걸린다.
맨 끝에 추가, 마지막 원소를 제거 O(1)
따로 배열을 변경할 필요 없기 때문에 O(1)이 걸린다.
임의의 위치에 원소 추가 O(N)
평균적으로 N/2 개를 밀어야 하기 때문이다.
책꽂이에 꽂힌 책들을 생각해보자. 중간에 책을 하나 꽂으려면, 나머지 책들을 옆으로 밀어야 한다.
임의의 위치에 원소 제거 O(N)
이 경우도 원소를 하나 제거하고, 평균적으로 N/2 개를 밀어야 하니까 O(N)의 시간이 필요하다.
insert 함수와 erase 함수를 직접 구현해보자
github 링크에 들어가서 코드를 받고 직접 삽입/삭제를 구현해보자.
존재하지 않는 인덱스를 참조하지 않도록 주의해야 한다.
배열 초기화 팁
1. memset 실수할 여지가 많다. 0이나 -1아닌 다른 값을 넣으면 오동작한다.
2. for 투박하지만 실수할 여지가 없어서 무난하다.
3. algorithm헤더의 fill함수 사용을 권한다.
실수할 여지도 별로 없고, 코드가 짧아서 가장 추천하는 방식이다.
int a[21];
int b[21][21];
// 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);
0x02 STL vector
배열과 거의 동일한 기능의 STL
배열과 달리 크기를 자유자재로 늘이고 줄일수 있는 장점이 있다.
공식 레퍼런스 사이트에서 확인하며 메서드 정확하게 익히도록 연습하기.
iterator는 따로 공부하는 것을 추천함
#include <bits/stdc++.h>
using namespace std;
int main(){
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};
v3.erase(v3.begin() + 2); // {1,2,4}
vector<int> v4; // {}
v4 = v3; // {1,2,4}
cout << v4[0] << v4[1] << v4[2] << '\n'; // 1 2 4
v4.pop_back(); // {1,2}
v4.clear(); // {}
}
시간 복잡도 유념할 점
앞에서 넣고 빼는 popfront(), pushfront() 는 O(N)의 시간이 걸리는 것을 유의하자.
insert(), erase()는 시간복잡도가 O(N)
뒤 쪽에 넣고 빼는 popback(), pushback()은 O(1)
벡터에서 = 를 사용하면 deep copy 가 발생한다.
vector 순회하는 방법
vector<int> v1 = {1,2,3,4,5,6};
// 1. range-based for loop (since C++11)
for(int e: v1)
cout << e << ' ';
// 2. not bad
for(int i = 0; i< v1.size(); i++)
cout << v1[i] << ' ';
// 3. 주의!
for(int i = 0; i <= v1.size()-1; i++)
cout << v1[i] << ' ';
1. range-based for loop 범위 기반 반복문 (C++11 부터 지원된 기능임을 유의)
2. v1.size()를 인덱스의 끝으로 보는 것
3. v1.size()는 기본적으로 unsized int를 반환함! 조심해야 함.
만약, v1이 빈 벡터일 때,
v1.size() -1 이 unsigned int 0에서 int1 을 빼는 식이 된다.
그리고 unsiged int 와 int를 연산하면 unsigned int 로 자동 형변환이 된다.
unsigned int 0 - (int) 1은 -1이 아니라, 4294967295 가 되어버린다!!
unsigned int overflow가 발생하여 런타임 에러가 난다.
0x03 배열 연습문제
배열 문제집을 풀어보자.
BOJ 10808번 알파벳 갯수
다음시간에는 연결리스트를 배우고 연습문제를 풀어본다.
공부 내용 출처 : 바킹독 알고리즘 0x03 배열
