0x00 정의와 성질
정의
성질
- O(1)에 k번째 원소를 확인/변경 가능
- 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
- Cache hit rate가 높음
- 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림
0x01 기능과 구현
어떤 배열에서
구현 - insert 함수
insert함수를 구현해 보면
void insert(int idx, int num, int arr[], int& len){
for(int i = len; i > idx; i--) //for문으로 순차적으로 값들을 오른쪽으로 이동시킴
arr[i] = arr[i-1];
arr[idx] = num; //새롭게 추가할 값을 넣기
len++; //용량이 부족하니 추가
}
구현 - erase 함수
erase함수를 구현해 보면
void erase(int idx, int arr[], int& len){
len --; //총 용량 줄이기
for(int i=idx; i < len; i++) //원소들을 한 칸씩 땡겨오기
arr[i] = arr[i+1];
}
전체를 특정 값으로 초기화 시킬때 어떤 방법이 제일 효율적인가
0x02 STL vector
vector는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱스를 가지고 각 원소로 접근할 수 있다. 그런데 vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있다.
.size() : vector의 크기
.begin() : 맨 앞 인덱스
.push_back(n) : 맨 끝에 n 원소 추가
.pop_back() : 맨 끝 원소 삭제
.clear() : 전체 원소 삭제
04, 05번째 줄 처럼 int e : v1 이라고 하면 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을 지원하지 않는다고 하면 사용할 수 없다.
0x03 연습문제
BOJ 10808번:알파벳 개수
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
for(char a = 'a'; a <= 'z'; a++){
int cnt = 0;
for( auto c : s)
if(a==c) cnt++;
cout << cnt << ' ';
}
}
0x01강의 연습문제
시간복잡도를 O(N) 으로 하기 위해 arr[] 말고도 for문안에 사용할(arr이 0이상 100이하라는 조건을 보고) 새로운 배열 occur을 크기 101로 만들어준다.
0으로 채워져있는 occur 배열을 길이 N만큼 반복해서 인덱스마다 값을 비교할것이다. 결국 arr[i]가 100이 되기 위해 필요한 수가 occur 인덱스가 되고 occur의 arr[i] 인덱스는 1로 바뀌어 가며 나중에 100이 되기 위해 필요한 수의 인덱스가 1인 경우 return 1을 해주게된다.
'공부 일지 > 알고리즘' 카테고리의 다른 글
[바킹독 알고리즘]0x06강 - 큐 (0) | 2023.12.26 |
---|---|
[바킹독 알고리즘]0x05강 - 스택 (0) | 2023.12.22 |
[바킹독 알고리즘]0x04강 - 연결 리스트 (0) | 2023.12.21 |
[바킹독 알고리즘]0x02강 - 기초 코드 작성 요령 II (0) | 2023.12.19 |
[바킹독 알고리즘]0x01강 - 기초 코드 작성 요령 I (0) | 2023.12.18 |