[실전 알고리즘] 0x03강 - 배열

1. 정의와 성질 배열 - 메모리 상에 원소를 연속하게 배치한 자료구조 배열의 성질 1. O(1)에 k번째 원소를 확인/변경 가능 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 3. Cache hit rate가 높음 4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 2. 기능과 구현 기능 1. 임의의 위치에 있는 원소를 확인/변경 = O(1) 2. 원소를 끝에 추가 = O(1) 3. 마지막 원소를 제거 = O(1) 4. 임의의 위치에 원소 추가/제거 = O(N) 구현 - insert, erase 함수 수정 전 코드 #include using namespace std; void insert(int idx, int num, int arr[], int &len) { len..

2022.01.21