배열의 성질
O(1)의 시간으로 k번쨰 원소를 확인/변경 가능- 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
- 메모리가 연속해서 존재하기때문에
Cache hit memory가 높다. - 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림
- 임의의 위치에 원소를 추가, 삭제하는 것은,
O(N)이다. - 마지막위치에 원소를 추가하거나 삭제하는 것은,
O(1)이다.
내 예제 풀이
void insert(int idx, int num, int arr[], int& len){
for(int i = len;i>idx;i--)
{
arr[i+1] = arr[i];
}
arr[idx] = num;
len++;
}
void erase(int idx, int arr[], int& len){
for(int i = idx;i<len;i++)
{
arr[i] = arr[i+1];
}
len--;
}예제 정답
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++;
}- 인덱스가 idx 인 원소를 옮겨야 하는데, idx+1인 원소까지 옮긴다는 생각으로 구현해버려서 오답처리 되었다.
- 또한 idx가 음수가 될 수 있음으로 범위에 항상 유의해야한다.
void erase(int idx, int arr[], int& len){
for(int i = idx;i<len;i++)
{
arr[i] = arr[i+1];
}
len--;
}- 배열의 크기 다행히 10으로 되어있어서 런타임에러가 발생하지 않았다.
- 만약 i가 len-1일때 i+1은 len이 되어서 배열의 크기가 꽉찬상태에서 수행하게 된다면 오류가 발생했을 것이다...
배열에 값을 채우는 방법
- 첫번째는
memset()함수를 이용하는 것이다. 하지만 오동작이 빈번하게 발생하니 사용을 지양하자. - 두번째는
이중 for문으로 원소하나씩 순회하면서 값을 채우는 방식이다. 직접구현해야한다는 단점이 있다. - 세번째는
algorithm헤더의fill()함수를 이용하는 것이다.
STL vector
- 배열과 마찬가지로
O(1)의 시간으로 값의 참조가 가능하다. - 배열에 비해 크기를 자유자재로 늘리고 줄일 수 있다는 장점이 있다.
v.size()로 현재 원소의 개수를 얻을 수 있다.v.push_back(x)v.pop_back(x)으로 마지막 원소를 추가하거나 삭제할 수 있으며 이때의 시간복잡도는O(1)이다.v.front(),v.back()으로 맨앞 혹은 마지막 원소에 접근할 수 있다.v.begin(),v.end()로 맨앞 혹은 마지막 원소의 주소값을 리턴받을 수 있다.v.insert(&index+a,x),v.erase(&index+a)로 원하는 인덱스의 값을 삭제하거나 삽입할 수 있다. 이때의 시간복잡도는O(N)이다.v.pop_front()v.push_front()로 맨앞의 원소를 삭제하거나 삽입할 수 있다. 이때의 시간복잡도는O(N)이다.=연산자로 벡터끼리의deep copy가 가능하다.
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
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}; // {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';
v4.pop_back(); // {1,2}
v4.clear(); // {}
}vector <int> v1 = {1,2,3,4,5,6};
for(int e : v1) // int &e를 통해 값의 변경을 할 수 있다.
cout << e << ' ';
for(int i = 0; i<v1.size(); i++)
{
cout << v1[i] << ' ';
}
for(int i = 0; i<=v1.size()-1 ; i++) // size()는 unsigned int를 반환한다. (오버플로우로 인한 런타임에러 발생)
{
cout << v1[i] << ' ';
}연습문제
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
string str;
cin >> str;
int arr[26];
fill(arr,arr+26,0);
for(char c : str)
{
arr[c-'a']++;
}
for(int x : arr)
cout << x << ' ';
return 0;
}정답
#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 << ' ';
}
}- 효울적이지 못한 코드 26번의 반복을 문자열의 모든 문자에 대해 수행하기 떄문!
#include <bits/stdc++.h>
using namespace std;
int freq[26];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
for(auto c : s)
freq[c-'a']++;
for(int i = 0; i < 26; i++)
cout << freq[i] << ' ';
}- 나의 풀이와 비슷한 코드 문자 하나마다 배열의 인덱스를 찾아가는 코드
연습문제2
Q. 주어진 길이 N의 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0이상 100이하이고 N은 1000이하이다.
시간복잡도는 O(N)이다.
내 풀이
int func2(int arr[], int N){
int visit[101];
fill(visit,visit+101,0);
for(int i = 0;i<N;i++)
{
if(arr[i] + visit[arr[i]] == 100)
return 1;
else
visit[arr[i]] = 1;
}
}- 틀린풀이다 ㅠㅠ if 조건문이 틀렸다. 배열을 0으로 초기화하는 방법을 fill()를 호출해서 시간 손해를 보고있다.
정답
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;
}
개발자 지망생