[바킹독의 실전 알고리즘] 0x03강 - 배열

 

정의와 성질

배열은 메모리 상에 원소를 연속하게 배치한 자료구조이다.

 

배열의 성질

• O(1)에 K번째 원소를 확인/변경 가능하다.
• 추가적으로 소모되는 메모리의 양(overhead)가 거의 없다.
• 메모리 상에 데이터들이 연속으로 배치되어 있어 Cache hit rate가 높다.
• 메모리 상에 연속된 구간을 잡아야 해서 할당에 다소 제약이 있다.

 

사용 팁

• memset 함수는 실수할 여지가 많다.
• for문은 투박하기는 하지만 실수할 여지가 없기 때문에 무난하고 좋다.
• algorithm 헤더의 fill 함수는 실수할 여지도 별로 없고 코드도 짧아 좋다.

 

STL vector

vector는 배열과 거의 동일한 기능을 수행하는 자료구조이다.

배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱스를 가지고 각 원소로 접근할 수 있다.

insert, erase의 시간 복잡도는 O(N), push_back, pop_back은 제일 끝에 원소를 추가하거나 빼는 것이어서 O(1)이다.

 

 

출처: 바킹독님 블로그