[코테/C++] 코테에서 자주 사용되는 C++ 자료구조 정리

C++의 장점 중 하나는

알고리즘 문제 풀이에 최적화된 다양한 자료구조를 사용할 수 있다는 점인 것 같다.

 

매우 다양한 자료구조들이 있는데,

그 중 초보자 수준에서 반드시 알아야 하는 자료구조들만 먼저 정리해본다.

 

vector, array, map, stack, queue 5개만 알아보자.

 

vector<타입>

vector는 배열의 길이를 알 수 없을 때 사용하는 동적 배열로

코테에서 가장 많이 사용되는 자료구조다.

 

일반 정적 배열과 유사하지만, 정적 배열과 달리 사용할 수 있는 메서드가 많고,

초기화 방법 등이 조금 다르다.

 

백준과 같이 모든 코드를 직접 작성하는 경우에는 정적 배열을 최대 크기로 선언하여 사용하기도 하지만

프로그래머스 같은 경우에는 문제에서 vector로 변수를 지정하는 경우가 대부분이다.

 

타입 자리에는 int, string 과 같은 타입이 들어갈 수 있고,

vector<int>, pair<int, int>와 같이 다른 자료구조가 들어갈 수도 있다.

vector<string> v;
vector<pair<int, int>> vp;
vector<vector<int>> vv;

 

vector도 array처럼 선언하면서 특정 길이와 값으로 초기화할 수도 있다.

모두 같은 값으로 초기화 할 때는 vector<타입> 변수명(길이, 초기화 값)

방식으로 초기화하는 것을 추천한다.

2차원 배열도 비슷하게 활용 가능하다.

vector<int> v(34, 0);
vector<vector<int>> vv(24, vector<int>(10, 0));

 

아래는 자주 사용되는 메서드들이다.

v.push_back(삽입할 값)

vector에 값을 집어넣는 메서드이다.

한 번에 하나의 값을 넣을 수 있다.

 

v.pop_back()

vector의 맨 뒤 값 하나를 삭제한다.

vector의 사이즈도 줄어든다.

 

v.erase(시작 이터레이터, 끝 이터레이터)

vector의 특정 구간의 값을 삭제한다.

vector의 사이즈도 그만큼 줄어든다.

하나의 요소만 삭제하고 싶다면, v.erase(삭제할 위치 이터레이터)로 

인자를 하나만 넣으면 된다.

 

시작 이터레이터 위치의 값은 포함, 끝 이터레이터 값은 제외되고 적용된다.

 

v.clear()

vector의 모든 요소를 삭제한다.

 

find(시작 이터레이터, 끝 이터레이터, 찾는 값)

vector에 귀속되지 않고 단독으로 사용하는 메서드이다.

find(v.begin(), v.end(), "값") 식으로 사용하면

vector가 특정 값을 포함하는지 확인할 수 있다.

값이 없다면 v.end()를 반환하며, 

있다면 해당 값의 이터레이터를 반환한다.

#include <bits/stdc++.h>
using namespace std;
vector<int> v;

int main() {
	v.push_back(1);
	v.push_back(100);
	v.push_back(103);
	v.push_back(1000);
	v.push_back(1005);
	for(int i : v) cout << i << ' '; //1 100 103 1000 1005
	cout << '\n';
	cout << v.size() << '\n'; //5
	
	v.pop_back();
	for(int i : v) cout << i << ' '; //1 100 103 1000 
	cout << '\n';
	cout << v.size() << '\n'; //4
	
	v.erase(v.begin(), v.begin() + 2);
	for(int i : v) cout << i << ' '; //103 1000 
	cout << '\n';
	cout << v.size() << '\n'; //2
	
	if(find(v.begin(), v.end(), 103) != v.end()) cout << "found\n"; //found
	cout << *find(v.begin(), v.end(), 103) << '\n'; //103
	if(find(v.begin(), v.end(), 300) == v.end()) cout << "not found\n"; //not found
	
	v.clear();
	for(int i : v) cout << i << ' '; //
	cout << '\n';
	cout << v.size() << '\n'; //0
	
}

 

array

정적 배열로

array에 붙여서 사용할 수 있는 별도의 메서드는 없다.

 

타입 변수명[길이] 형태로 선언한다.

보통 문제에서 주어지는 최대 값으로 길이를 선언하여 필요한 부분만큼 사용한다.

int a[4];
int b[100][100];

전역 변수로 배열을 선언하면

모든 값이 0으로 초기화된다.

 

굳이 vector를 사용하지 않아도 되는 단순한 문제나,

2차원 배열에 많이 사용한다.

 

map<key타입, value 타입>

map은 자바스크립트에도 있는 자료구조라 익숙한데,

key-value로 쌍을 이뤄 값을 저장하는 구조다.

 

일명 사전형이라고도 하여,

사전과 유사하게

특정 값으로 다른 값을 호출해야 하는 문제에서 많이 사용한다.

 

C++의 map은 자동으로 key값 기준 오름차순 정렬이 된다.

for문으로 탐색할 때 넣은 순서가 아닌 

아스키코드순 오름차순으로 탐색되기 때문에 주의해야 한다.

 

map<key 타입, value 타입> 변수명으로 선언하며,

map에 귀속하여 사용할 수 있는 메서드들은 아래와 같다.

 

mp.insert({key, value})

key와 value를 쌍으로 삽입해야 한다.

 

mp[key] = value

insert를 사용하지 않고도

= 연산자로 키에 값을 할당할 수 있다.

이미 값이 있는 키에 재할당도 가능하다.

 

mp[key]

키로 값을 참조할 수 있다.

주의할 점은, 값이 할당된 적 없는 key를 mp[key]로 조회하면

그 key에 value가 int형인 경우 0, string형인 경우 빈문자열이 할당되어 요소가 저장된다.

의도치 않게 값이 할당될 수 있으니 주의하자.

 

mp.size()

map의 사이즈를 호출하는 메서드로,

key-value 쌍의 개수를 알려준다.

 

mp.erase(key)

특정 key-value 쌍을 삭제할 수 있다.

 

mp.find(key)

특정 키를 가진 요소를 찾아 이터레이터를 반환한다.

없는 경우 mp.end()를 반환한다.

 

mp.clear()

map의 모든 요소를 삭제한다.

 

for(auto it : mp)

일반적인 for문이지만, map에도 사용할 수 있기에 정리해봤다.

it에서 it.first, it.second로 key-value를 뽑아 사용할 수 있다.

for(auto it = mp.begin(); it != mp.end(); it++)

마찬가지로 map을 순회하는 구문이다.

#include <bits/stdc++.h>
using namespace std;

map<string, string> mp;
int main() {
    mp.insert({"duck", "quek quek"});
    mp.insert({"dog", "wal wal"});
    
    for(auto it : mp) cout << it.first << ' ' << it.second <<'\n'; 
    /*
    dog wal wal
    duck quek quek
    */
    cout << mp.size() << '\n'; //2
    
    mp["chicken"] = "ppiyak";
    cout << mp["chicken"] <<'\n'; //ppiyak
    cout << mp.size() <<'\n'; //3
    
    mp.erase("dog");
    for(auto it : mp) cout << it.first << ' ' << it.second <<'\n';
    /*
    chicken ppiyak
    duck quek quek
    */
    cout << mp.size() << '\n'; //2
    
    if(mp.find("person") == mp.end()) cout << "not found\n"; //not found
    mp["person"];
    if(mp.find("person") != mp.end()) cout << "found\n"; //found

    mp.clear();
    cout << mp.size() << '\n'; //0
	
	return 0;
}

 

stack<타입>

stack은 쌓여있는 접시처럼

처음에 넣은 요소가 가장 밑에 들어가고

나중에 넣은 요소가 그 위 쌓여

가장 마지막에 넣은 요소에만 접근할 수 있는 자료구조이다.

 

[{(  )}] 같은 괄호 맞추기 문제나,

탐색 등에 사용된다.

 

stack<int> stk;

stack<string> stk;

와 같은 형태로 선언한다.

 

사용되는 메서드에는 아래 4가지가 있다.

stk.push(값)

stack에 값을 집어넣는다.

집어넣은 값은 가장 위에 쌓이게 된다.

 

stk.pop()

stack 가장 위의 값을 삭제한다.

자바스크립트의 pop처럼 삭제하는 값을 반환하지는 않으니 주의하자.

 

stk.top()

stack의 가장 위 값을 호출한다.

보통은 stk.top()으로 값을 확인하고,

stk.pop()을 이어 사용하는 방식으로 많이 쓰인다.

 

stk.size()

stack에 담긴 요소의 개수를 확인할 수 있다.

#include <bits/stdc++.h>
using namespace std;
stack<int> stk;
int main() {
    stk.push(1);
    stk.push(202);
    stk.push(333);
    cout << stk.top() << '\n'; //333
    cout << stk.size() <<'\n'; //3 
    
    stk.pop();
    cout << stk.top() << '\n'; //202
	cout << stk.size() <<'\n'; //2
	
	return 0;
}

 

queue<타입>

queue는 stack과 반대로

먼저 넣은 것에만 접근이 가능한 자료구조다.

 

먼저 넣은 것이 가장 앞으로 가고,

제일 앞의 값을 호출하고, 삭제할 수 있다.

 

메서드는 push(), pop(), size()는 stack과 같고,

top()대신 front()를 사용한다.

 

pop()은 가장 앞의 값을 삭제한다.

 

문제 풀 때 stack보다는 사용 빈도가 낮은 것 같다.

#include <bits/stdc++.h>
using namespace std;
queue<string> q;
int main() {
    q.push("hi");
    q.push("bye");
    q.push("annyeong");
    
    cout << q.front() << '\n'; //hi
    cout << q.size() << '\n'; //3
    
    q.pop();
    cout << q.front() << '\n'; //bye
    cout << q.size() << '\n'; //2
    
	return 0;
}