코딩 테스트 문법 - STL의 컨테이너

Vector

배열과 유사한 컨테이너. 데이터를 순차적으로 저장하고, 인덱스를 통해서 특정 위치의 원소에 쉽게 접근할 수 있음.

사용하기 위해서는 #include <vector> 헤더 포함 필요.

 

선언

1차원 벡터

vector<int> v;
vector<int> v2 = {1,2,3,4,5}; //길이가 5인 벡터, 내부의 값들을 개별 초기화(1,2,3,4,5)
vector<int> v3(4,3); //길이가 4인 벡터, 내부의 값들은 모두 3으로 초기화
vector<int> v4(v3); //v3을 복사

 

 

2차원 벡터

vector<vector<int>> v1;

int rows = 3;
int cols = 4;
vector<vector<int>> v2(rows, vector<int>(cols)); // row 3, column 4인 배열 생성. 이때 값들은 0이 아닌 무작위의 쓰레기값들로 채워짐.

int val = 5;
vector<vector<int>> v3(rows, vector<int>(cols, val)); //모든 원소 값을 val로 초기화

vector<vector<int>> v4 = {
	{1, 2, 3},
    	{4, 5, 6},
    	{7, 8, 9},
}; // 직접 초기화

 

 

삽입과 삭제

벡터는 배열로 구성되어 있기 때문에 맨 뒤에 값을 추가(삽입)하거나 삭제는 효율적으로 가능하지만, 맨 앞에 값을 추가하거나 삭제할때는 비효율적입니다. 뒤의 원소들을 한칸씩 모두 이동해줘야 하기 때문입니다.

맨 앞에 원소를 삽입할때는 insert(삽입할 주소, 삽입할 값) 메서드를 사용하면 됩니다. 이때 삽입할 주소를 얻는 방법은 begin() 함수를 사용하면 됩니다. v.begin()은 vector v의 시작 주소를 나타냅니다.

맨 앞의 원소를 삭제할때는 erase() 메서드를 사용하고, 사용 방법은 insert 메서드와 동일합니다.

맨 앞에 원소를 삽입 또는 맨 앞의 원소를 삭제하는 연산의 시간 복잡도는 O(N)입니다. 맨 앞의 원소를 제어할 일이 많다면 벡터 대신 덱(Deque)을 사용하는것이 좋아보입니다.

 

맨 뒤에 원소를 삽입할때는 push_back() 메서드를 사용하고, 맨 뒤의 원소를 삭제할때는 pop_back() 메서드를 사용하면 됩니다.

 

Set

Set은 중복을 허용하지 않고, 데이터를 자동으로 정렬하는 컨테이너입니다. 사용하기 위해서는 #include <set> 헤더를 포함해야 합니다.

 

선언

set<int> s1;
set<int> s2 = {3,1,2,5} // => 실제로는 {1,2,3,5}로 들어감
set<int> s3(s2);

 

원소 탐색

find()메서드를 사용하면 됩니다. 이때 찾으려는 값이 set안에 존재하지 않으면 end반복자를 반환합니다.

시간 복잡도는 O(logN)입니다.

set<int> numbers = {1,2,3,4,5};
auto it = numbers.find(3); // it = 3의 위치 주소. 값을 얻기 위해서는 *it으로 읽을 수 있음
auto it2 = numbers.find(9); // it2 = numbers.end(), 9는 set 안에 없음.

 

삽입과 삭제

Set은 모든 위치에서의 삽입/삭제 시간 복잡도는 O(logN)입니다.

삽입시에는 insert(삽입할 값), 삭제시에는 erase(삭제할 값 또는 주소) 메서드를 사용합니다.

 

Map

키와 값을 쌍으로 갖는 컨테이너입니다. 사용하기 위해서는 #include <map> 헤더를 포함해야 합니다.

키와 값의 쌍은 entry라고 하며, std::pair타입으로 표현합니다.

Map의 내부는 항상 키값을 기준으로 데이터가 자동 정렬됩니다. 검색, 삽입, 삭제시 시간 복잡도는 O(logN)입니다.

맵의 키 값은 중복되지 않고 유일하고, 정수 뿐만 아니라 문자열도 키값으로 사용할 수 있습니다.

 

선언

map<string, int> employees;

map<string, int> grades = {
	{"Jin", 4},
    	{"Ali", 2}
    };

 

특정 키에 접근, 값 변경

[]를 입력하여 직접 접근할 수도 있고, find()메서드를 활용하여 grades.find("Jin") 형태로 사용할 수 있습니다.

이때 []연산자를 통해 특정 키에 접근하려고 할때 해당 키가 맵에 없으면 맵에 현재 키를 추가한다는 것을 유의해야 합니다.

따라서 접근을 진행하면서, 특정 키가 없는 상태를 유지해야 한다면 find() 메서드를 사용해야 합니다. 키가 없다면 find() 메서드는 end 반복자를 반환하며, find() 메서드의 시간 복잡도는 O(logN)입니다.

 

각 원소는 pair 타입의 객체이고, 키는 first, 값은 second에 저장되어 있습니다.

 

값을 변경할때는 [] 연산자를 활용하여 수정해주면 됩니다.

map[4] = "Apple";

mapStr["Banana"] = 30;

 

삽입과 삭제

[]를 사용하면 키가 없을때 원소 삽입이 바로 가능합니다. 추가로 insert() 메서드를 사용하면 삽입이 가능합니다.

insert로 삽입시 pair타입의 객체를 만들기 위해 make_pair() 메서드를 사용합니다.

삽입 연산의 시간 복잡도는 O(logN)입니다.

 

삭제할때는 erase() 메서드를 사용하며, 인수로 키값 또는 키의 위치를 넣으면 해당 키 또는 해당 위치의 원소가 삭제됩니다.

인수로 값을 넘길때의 시간 복잡도는 O(logN), 위치(주소)를 넘길때 시간 복잡도는O(1)입니다.

 

 

Unordered_Set & Map

Set이나 Map을 사용해야 하는데 굳이 정렬까지는 필요 없을때는 <unordered_map>, <unordered_set>을 사용합니다. 데이터를 자동으로 정렬하지 않기 때문에 삽입, 삭제, 탐색의 시간 복잡도는 O(1)입니다.