array,vector,range-based for loop
J-Shine
바킹독님의 실전알고리즘배우기 3강듣고 요약
배열의 성질
배열의 공간 지역성 때문에 cache hit rate가 높다.
insert와 erase 함수의 구현 &
#include <bits/stdc++.h>
using namespace std;
void insert(int idx, int num, int arr[], int& len){
for(int i = len; i > idx; i--)
arr[i] = arr[i-1];
arr[idx] = num;
len++;
}
void erase(int idx, int arr[], int& len){
len--;
for(int i = idx; i < len; i++)
arr[i] = arr[i+1];
}
void printArr(int arr[], int& len){
for(int i = 0; i < len; i++) cout << arr[i] << ' ';
cout << "\n\n";
}
void insert_test(){
cout << "***** insert_test *****\n";
int arr[10] = {10, 20, 30};
int len = 3;
insert(3, 40, arr, len); // 10 20 30 40
printArr(arr, len);
insert(1, 50, arr, len); // 10 50 20 30 40
printArr(arr, len);
insert(0, 15, arr, len); // 15 10 50 20 30 40
printArr(arr, len);
}
void erase_test(){
cout << "***** erase_test *****\n";
int arr[10] = {10, 50, 40, 30, 70, 20};
int len = 6;
erase(4, arr, len); // 10 50 40 30 20
printArr(arr, len);
erase(1, arr, len); // 10 40 30 20
printArr(arr, len);
erase(3, arr, len); // 10 40 30
printArr(arr, len);
}
int main(void) {
insert_test();
erase_test();
}
배열의 멤버를 모두 특정 값으로 초기화시키기
2번 for문을 직접 돌리거나,
3번 fill 함수를 이용하면 좋다.
(1번은 실수할 여지가 있다.)
vector 사용하기
vector에서는 iterator(v.begin())를 이용하고,
v.push_back(), v.pop_back() -> O(1)
v.insert(), v.erase() -> O(N) 등 함수롤 이용하여 데이터를 수정한다.
range-based for loop(C++11 이상) 사용하면 편하다.
3번처럼 vector를 쓰면 무한루프에 빠지게 된다.
-> vector는 unsigned int를 반환하기 때문에 0보다 작은 값이 없다.
따라서 0 - 1 = 4294967295(2^32-1)가 된다.
range-based for loop를 쓰면 for문을 돌기 편리하다.
연습문제 1
연습문제 2
내 풀이
int freq[100] = { 0 };
int func2(int arr[], int N) {
for (int i = 0; i < N; i++) {
freq[arr[i] - 1]++;
}
for (int i = 0; i < N; i++) {
if (freq[100 - arr[i] - 1] >= 1) return 1;
}
return 0;
}
이렇게 하면 arr[i]가 0일 때 freq[-1]에 접근하기 때문에 runtime error가 발생할 수 있다고 바킹독님께서 지적해주셨다
(오류를 지적해주셔서 감사합니당ㅎㅎ 앞으로도 누구든지 블로그 글에 대한 오류가 있으면 지적해주시면 감사하겠습니다!)
그래서 실제로 돌려봤는데 띠용하는 일이 벌어져서 그것에 대한 자세한 사항은 이 글에 적어두었다.
또한 말씀해주신 대로 고친 풀이는 아래와 같다.
고친 풀이
int freq[101] = { 0 };
int func2(int arr[], int N) {
for (int i = 0; i < N; i++) {
freq[arr[i]]++;
}
for (int i = 0; i < N; i++) {
if (freq[100 - arr[i]] >= 1) return 1;
}
return 0;
}
baaaaaaaarkingDog님의 풀이
int func2(int arr[], int N){
int occur[101] = {};
for(int i = 0; i < N; i++){
if(occur[100-arr[i]] == 1)
return 1;
occur[arr[i]] = 1;
}
return 0;
}