💡 배열
🍎 정의
- 메모리 상에 원소를 연속하게 배치한 자료구조
🍍 성질
- O(1)에 k번째 원소를 확인/변경 가능하다.
- 추가적으로 소모되는 메모리의 양(overhead)가 거의 없다.
- Cache hit rate가 높다.
- 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다.
🥝 시간 복잡도
- 원소를 끝에 추가 : O(1)
- 원소를 마지막에 추가 : O(1)
- 임의의 위치에 원소를 추가 : O(N)
- 임의의 위치에 있는 원소를 제거 : O(N)
🍉 구현
// 원소 추가
#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++;
}// 원소 삭제
#include <bits/stdc++.h>
using namespace std;
void erase(int idx, int arr[], int& len) {
len--;
for (int idx; i < len; i++)
arr[i] = arr[i+1];
}🍑 Tip
-
전체를 특정 값으로 초기화 시키는 효율적인 방법
- memset 함수를 활용 → 하지만 실수할 여지가 많기 때문에 비추천
- for문을 돌며 값을 하나 하나 바꾸는 방식
- 알고리즘 헤더의 fill 함수를 이용 → 추천!
int a[21]; int b[21][21]; // 1.memset memset(a, 0, sizeof a); memset(b, 0, sizeof b); // 2. for for (int i = 0; i < 21; i++) a[i] = 0; for (int i = 0; i < 21; i++) for (int j = 0; j < 21; j++) b[i][j] = 0; // 3. fill fill(a, a+21, 0); for (int i = 0; i < 21; i++) fill(b[i], b[i] + 21, 0);
💡 STL Vector
🍏 정의
- 배열과 거의 동일한 기능을 수행하는 자료구조
- 원소가 메모리에 연속하게 저장되어 있다.
- 인덱스를 가지고 원소에 접근 : O(1)
- 배열과 달리 크기를 늘리거나 줄일 수 있다.
🍊 원소의 추가/삭제
#include <bits/stdc++.h>
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;
cout << v4[0] << v4[1] << v4[2] << '\n'; // 124
v4.pop_back(); // {1, 2}
v4.clear(); // {}
}- insert, erase : O(N)
- push_back, pop_back(제일 끝에 원소 추가/삭제) : O(1)
- vector에서 = 을 사용하면 deep copy가 된다.
→ v4를 바꿔도 이후 v3에 영향을 주지 않음
🍈 순회
vector<int> v1 = {1, 2, 3, 4, 5, 6};
// 1. range-based for loop (since C++ 11)
for (int e : v1)
cout << e << ' ';
// 2. not bad
for (int i = 0; i < v1.size(); i++)
cout << v1[i] << ' ' ;
// 3. ***WRONG***
for (int i = 0; i <= v1.size()-1; i++)
cout << v1[i] << ' ' ;- range-based for loop
- int e : v1에서 복사된 값이 e에 들어가고, int& e : v1은 원본이 e에 들어간다.
- 코딩 테스트에서 C++ 11을 지원하지 않으면 사용 불가능
- 3번은 잘못된 코드
- vector의 size는 unsigned int를 반환
- v1이 빈 vector일 경우 v1.size() - 1은 unsigned int 0에서 1을 빼게 됨
- unsigned int와 int를 연산하면 unsigned int로 자동 형 변환 발생
→ -1이 아니라 4296967295가 됨 (unsigned overflow)
→ 런타임 에러 발생
💡 문제 풀이
🍇 BOJ 10808 알파벳 개수
#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] << ' ';
}🍋 O(N^2) -> O(N) 풀이
- 주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라.
arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.
-> O(N) 풀이법
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;
}끗~,,
