[C++] 코딩테스트 때 자주 사용하는 STL 및 알고리즘 정리

1. 개요

코딩테스트 문제를 풀다보면 STL을 많이 사용하게 된다. 내가 자주 사용하는 것들을 까먹지 않게 좀 정리해본다.

원래 SW를 개발할 때는 namespace를 붙이지 않고 개발하는 게 좋지만, 코딩테스트의 편의성을 위해서 아래와 같이 선언해준다.

using namespace std;

대부분의 자료 구조는 4가지의 기본 연산을 갖고 있다. 따라서 지금부터 나열할 STL은 아래의 기준으로 나열한다.

1. 읽기 : Read
2. 탐색 : Search
3. 삽입 : Insert
4. 삭제 : Delete

여기서 어느 정도 눈치챈 사람들이 있겠지만, 앞으로 나올 STL은 위의 4가지 연산마다 저마다의 장점을 갖고 있다.

 

2. Vector

배열 관련하여 사용할 때는 vector를 줄구장창 사용할 것이다. 아래와 같이 코드가 선언되어 있다고 가정하자.

#include <vector>

using namespace std;

int main()
{
  vector<int> v;

  return 0;
}

2-A. 읽기

읽기는 대괄호를 이용해서 해당 값을 읽으면 된다.

cout << v[0] << endl;

2-B. 탐색

탐색을 위해서는 std::find를 이용하여 2가지 방법이 있다.

// 1. 반복자(iterator) 찾기
auto iter = std::find(v.begin(), v.end(), 178);

// 2. 인덱스(index) 찾기
auto idx = std::find(v.begin(), v.end(), 178) - v.begin();

// 만약에 없으면?
if ( std::find(v.begin(), v.end, 178()) == v.end() );

std::find() 함수를 이용하며, 해당 요소가 vector에 존재하지 않으면 v.end()를 반환한다. 이 함수의 반환값은 반복자이며, 해당 반복자에 해당하는 인덱스를 얻고 싶다면 첫번째 반복자 v.begin()을 빼주면 된다.

Iterator를 이용하여 인덱스를 얻는 방법이 하나 더 있다. 바로 distance() 함수를 이용하여 아래와 같이 사용가능하다.

#include <algorithm>

auto index = std::distance(v.begin(), iter);

2-C. 삽입

삽입은 insert()를 이용하며 아래와 같이 사용한다.

v.insert( v.begin(), 100 ); // 100을 제일 처음에 추가
v.insert( v.begin()+5, 5 ); // 5를 (처음+5)에 추가
v.insert( v.end(), 9 ); // 9를 제일 마지막에 추가

2-D. 삭제

삭제는 erase()를 이용하며 아래와 같이 사용한다.

v.erase( v.begin() ); // 제일 첫 번째 원소 제거
v.erase( v.end()-1 ); // 마지막에서 한 칸 앞에 원소 제거

3. Map

<map> 정말 많이 사용한다. 전화번호부, 메뉴판과 같이 이름-전화번호 혹은 메뉴-가격 이렇게 key-value의 쌍으로 표현할 수 있을 때라던지, 투표소에서 누가 투표를 안 했는가?에 대한 문제도 손쉽게 해결 가능 하다. 기본 자료 구조는 해시 테이블(hash table) 또는 트리(tree)이다. 기본 선언은 아래와 같다.

#include <map>

// 또는

#include <unordered_map> // 필자는 이걸 더 선호한다.

/*
  사용하는 곳 안에서 (대게 main문)
  key-value의 쌍(pair)로 선언해야 하므로 2가지를 <> 안에 넣어줘야 한다.
*/
unordered_map<string, int> um;
um["bigbigpark"] = 1234;   // 문자열 bigbigpark이라는 key에 저장된 value는 정수형 1234이다.

3-A. 탐색

탐색은 find 메소드를 이용해준다. 위에 vector는 std::find를 이용해주었다. 차이점을 주의하자.

if ( um.find("bigbigpark") != um.end() ) // 찾지 못한다면 end()를 반환

// 만약 찾았으면?
/*
  앞서 말했다시피 map 자료구조는 key-value 두 가지로 구성되어 있다.
  따라서 찾았을 때 두 가지 모두 접근이 가능하다.
*/
auto iter = um.find("bigbigpark");

auto key   = iter->first;  // key에 접근한다. -> 문자열 bigbigpark 반환.
auto value = iter->second; // value에 접근한다. -> 정수형 1234 반환.

3-B. 삽입

여러 방법이 있지만 나는 아래와 같이 사용한다.

um["Eric"] = 9999;

3-C. 삭제

key를 기준으로 삭제한다.

um.erase["Amanda"]; // 없으면 um.end()를 반환한다.

3-D. 반복문 순회

// vector의 경우 아래와 같이 반복문을 순회하며 값에 접근이 가능하다.
vector<int> v = {1, 2, 3, 4, 5};
for(auto n: v)
{
  std::cout << n << std::endl;
}

// map의 경우 어떨까?
unordered_map<string, int> um;
um["A"] = 1111;
um["B"] = 2222;

for(auto it: um)
{
  // key-value의 특성에 따라 접근하면 된다.
  std::cout << "key  : " << it->first << std::endl; // 문자열 A, B 출력
  std::cout << "value: " << it->second << std::endl; // 정수형 1111, 2222 출력
}

4. 문자열(String)

애증의 녀석. C++ 코테에 문자열은 빠지면 정말 섭섭하다. 큰 수 입력받을 때 9999999999999999도 string으로 받으면 된다. 아래와 같이 선언한다.

#include <string>

string s = "bigbigpark";

4-A. 찾기

find() 메소드를 사용하긴 하지만, 찾지 못하였을 때 반환값이 다름에 주의하자.

if ( s.find("big") != std::string::npos )

find() 메소드에는 다음과 같은 특성들이 있다.

1. 못 찾았을 시 반환값은 std::string::npos이다.
2. 찾았을 때 반환값은 해당 인덱스이다.
3. 중복되는 문자의 경우 제일 먼저 등장한 인덱스를 반환해준다.

4-B. 교체

replace() 메소드를 사용한다.

int pos = 3;
int length = 5;
string 문자열 = "name";

/*
  pos위치에서 length길이만큼 문자열로 채우게 된다.
  pos위치와 length와 문자열 길이의 차이로 인한 에러는.. 각자 센스로 해결하자.
*/
s.replace(pos, length, 문자열);

4-C. 삭제

// 1.
s.erase(pos, len); // pos위치에서 len길이만큼 삭제한다.

// 2.
s.erase(s.begin()+2); // 처음 위치+2 에 있는 녀석을 삭제한다.

// 3.
s.erase(s.begin()+1, s.end()-3) // 첫 번째 위치 ~ 두 번째 위치까지의 요소들을 삭제한다.

자 ! 여기서 특정 문자만 제거하기를 해보자

/*
  A는 문자열이 아닌 char 형으로 들어감에 주의하자.
  문자열 s에서 'A'가 들어간 부분을 모조리 지워준다.
*/
s.erase( std::remove(s.begin(), s.end(), 'A'), s.end() )

4-D. 문자열 부분 추출

삽입, 삭제 말고 이미 존재하는 문자열에서 조금만 떼올 순 없나?
있다.

// 1. 전체 가져오기
string new_string = s.substr();

// 2. 5번 인덱스부터 끝까지 가져오기
string new_string = s.substr(5);

// 3. 5번 인덱스부터 1길이만큼 가져오기
string new_string = s.substr(5, 1);

4-E. 문자열 형변환

정말정말 많이 나온다. 자주 사용하면 거의 외울 수 있을 듯 ?

// char -> string, 문자열 객체 선언후 그냥 더하기.
char ch = 'A';
string temp = "";
temp += ch;

// string -> char, 그냥 인덱싱 하자.
string str = "bigbigpark";
char c = str[0];

// int -> string
int num = 5;
string str = to_string(num);

// string -> int 또는 double
string n_str = "1122";
int n1 = stoi(n_str);
double n2 = stod(n_str);

// char -> int
// 자릿수 연산에 많이 등장한다.
char ch = '9';
int n = ch - '0'; // '0'를 빼게 되면 보이는 그대로 숫자가 저장되게 된다.

추가적으로 ASCII 숫자 맵핑 관계를 알아보자

1. AZ: 6590
2. az: 97122

4-F. 문자열 공백으로 분리

공백 말고 다른 구분자(delimeter)으로도 분리 가능!

#include <sstream>
#include <string>

// 공백이 포함된 문자열이 있다고 가정하자.
string str = "hello world this is park";
istringstream ss(str);

string word;

// getline() 3번째 인자에 구분자를 설정해주자. 아래 예시는 공백.
while ( getline(ss, word, ' ') )
{
  std::cout << word << std::endl;
}

---

여기까지 내가 코테를 봐 오면서 시험 쳐온 현황이다. 다음은 함수를 몇 가지 알아보자.

5. 정렬

숫자를 오름차순/내림차순으로 정렬해보자.

#include <algorithm>
#include <vector>

using namespace std;

vector<int> v = {4, 2, 3, 5, 1};

// 오름차순
sort( v.begin(), v.end() );

// 내림차순
sort( v.begin(), v.end(), greater<>() );

6. 합

vector 요소의 합을 구해보자. 물론 반복문 선언해서 하나하나 다 더해도 됨.

#include <numeric>

// 합
auto sum = accumulate( v.begin(), v.end(), 0);

// 평균
auto avg = sum / n.size();

7. 이진수 연산

이진수를 위한 라이브러리가 있는지 최근에 알았다. 정말 편리하구나 ㅜㅜ

7-A. 선언 및 사용

#include <bitset>
/*
  1) 이진수 형태의 문자열을 바로 사용 가능.
  2) 십진수를 이진수로 바로 사용 가능.

  이진수 형태의 덧셈 뺄셈 가능
*/
int n1 = 544132;
string n2 = "01110111011";

bitset<16> bit; // 모든 16자리 비트가 0으로 초기화됨.
bitset<16> bit (n1); // 정수형을 바로 비트연산 가능
bitset<16> bit (n2); // 문자열을 바로 비트연산 가능

7-B. 이진수를 다시 문자열/정수형으로 변환

auto i_num = bit.u_long();    // 이진수를 정수형으로 변환
auto s_num = bit.to_string(); // 이진수를 문자열로 변환

7-C. 메소드들

1. flip(n) : n번째 비트 반전 시키기
2. test(n) : n번째 비트가 1인지 검사 (맞으면 true, 다르면 false) 반환