[C++] STL 자료구조: array, vector

배열은 같은 자료형의 원소들을 메모리 상의 연속적인 위치에 저장하는 자료구조이다.

- 크기는 항상 고정이며 원소의 삭제는 불가능하다.

- 여기서 원소의 삭제는 { 1, 2, 3 }을 { 1, 2, * }으로 바꾸는 것이 아니라 { 1, 2 }처럼 아예 한 칸을 삭제하는 것을 의미한다.

마찬가지로 원소의 삽입 또한 불가능하다.

 

vector

c++ STL에서 가장 많이 사용되는 자료구조이다.

위의 정적인 배열과 달리 vector는 크기가 가변적인 동적 배열으로,

배열과 마찬가지로 임의 위치의 원소를 O(1)에 접근 및 수정할 수 있으며, 메모리 상의 연속적인 위치에 존재한다.

차이점은 크기를 런타임에 변경할 수 있으며, 원소의 삽입 및 삭제를 지원한다.

이때 삽입 및 삭제는 맨 뒤의 원소일 경우 O(1), 중간에 위치한 원소일 경우 O(n)에 수행된다.

vector<vector<int>> v3; // v3는 각 원소가 벡터이기 때문에 v3[i][j]와 같이 2차원 배열처럼 사용할 수 있다.

 

===잘 사용하는 함수===

vector<int> v(3), t(2, 5); // v = { 0, 0, 0 }, t = { 5, 5 }
vector<vector<int>> w(2, vector<int>(3, -1)); // w = { { -1, -1, -1 }, { -1, -1, -1 } }

v.push_back(1); // v = { 0, 0, 0, 1 }
v.pop_back(); // v = { 0, 0, 0 }
v.insert(v.begin(), 2); // insert 2 at v[0], v = { 2, 0, 0, 0 } 처음 위치에 2 삽입
v.insert(v.begin() + 2, 3, 4); // insert { 4, 4, 4 } at v[2], v = { 2, 0, 4, 4, 4, 0, 0 } 3개의 4를 삽입
v.insert(v.begin(), t.begin(), t.end()); // insert [t.begin(), t.end()) at v.begin(), v = { 5, 5, 2, 0, 4, 4, 4, 0, 0 }
v.erase(v.begin() + 2); // erase v[2], v = { 5, 5, 0, 4, 4, 4, 0, 0 }
v.erase(v.begin(), v.begin() + 6); // erase [v[0], v[6]) v = { 0, 0 }

cout << "v.size() : " << v.size() << '\n'; // 2
cout << "v.empty() : " << v.empty() << '\n' << '\n'; // 0
v.clear(); // v = { }
v.resize(1); // v = { 0 } 
v.resize(3, 2); // v = { 0, 2, 2 }
v[1] = 1; // v = { 0, 1, 2 }

for (auto it = v.begin(); it != v.end(); it++) {
cout << "pos : " << it - v.begin() << ", v[pos] : " << *it << '\n';

//begin은 첫번째 요소를 가리키는 iterator를 반환

// it-v.begin()은 it가 시작 위치로부터 얼마나 떨어졌는지(거리) 즉 0,1,2,3,4,5...를 반환한다

//v[pos]는 그 위치의 값을 반환한다.
}
cout << '\n';

for (auto it = v.rbegin(); it != v.rend(); it++) {
cout << "pos : " << it - v.rbegin() << ", v[pos] : " << *it << '\n';
}
cout << '\n';

//rbegin은 begin이 reverse된거다 현재 vector의 맨 끝을 가리킨다.

//따라서 it-v.rbegin()은 v[pos] 값을 반대로 출력된다( vector에 있는 거꾸로 )

cout << "v.front() : " << v.front() << '\n'; // 0
cout << "v.back() : " << v.back() << '\n'; // 2

 

<참고>

begin(), end() 등의 반환값은 c++의 STL 자료구조에 정의되어있는 iterator(반복자) 중 하나이다.

iterator는 포인터처럼 자료구조의 원소를 가리키는 자료형으로 몇 가지 유용한 연산들을 제공한다.

 

<백준>

==> 문자열의 갯수 저장: cnt1[a[i] - 'a']++

10807) 총 숫자 개수 입력 -> 띄어쓰기로 숫자 입력 -> 개수를 알고 싶은 숫자 입력 -> 숫자 몇 개인지 출력

int main() {
fastio;
int n; cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
int m, cnt = 0; cin >> m;
for (int i = 0; i < n; i++) {
if (v[i] == m) cnt++;
}
cout << cnt << '\n';
}

 

10808) 영단어 입력->각 알파벳 몇개인지 (a~z까지) 
int main()
{
fastio;
string s; cin >> s;
vector<int> cnt(26);
for (int i = 0; i <s.size(); i++) {
cnt[s[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
cout << cnt[i] << ' ';
}
cout << '\n';

}

 

2577)A,B,C 입력 후 A*B*C 계산 결과에서 0~9 각각 몇 개인지 세기

int main() {
fastio;
int a, b, c; cin >> a >> b >> c;
string s = to_string(a * b * c);
vector<int> cnt(10);
for (int i = 0; i < s.size(); i++) cnt[s[i] - '0']++;
for (int i = 0; i < 10; i++) cout << cnt[i] << '\n';
}

string s;하고 s.size()는 문자열의 길이이다. s[i]는 문자열의 각 요소이다.

vector <int> v; 하고 v.size()는 벡터에 저장된 요소의 개수이다.

==> vector랑 유사하다.

 

1919) 애너그램

#include <iostream>
#include <string>
#include <vector>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int main() {
fastio;
string a, b;
int count = 0;
cin >> a>> b;
vector<int> aalph(26);
vector<int> balph(26);
for (int i = 0; i < a.size(); i++) {aalph[a[i] - 'a']++; }
for (int i = 0; i < b.size(); i++) {balph[b[i] - 'a']++; }
for (int k = 0; k < 26; k++) { count += abs(aalph[k] - balph[k]); }
cout << count<<'\n';
}

 

11328)Strfry

int main(void){
    fastio;
    int N; cin>>N;
    while(N--){
        string a,b;
        cin>>a>>b;
        vector<int> cnt(26);
        for(int i=0; i<a.size(); i++) cnt[a[i]-'a']++;
        for(int i=0; i<b.size(); i++) cnt[b[i]-'a']--;
        bool flag =1;
        for(int i=0; i<26; i++) if(cnt[i]) flag=0;
        cout<<(flag? "Possible":"Impossible")<<'\n';
    }
    
}