알고리즘 풀이에 사용되는 언어는 C++과 파이썬이 양분하고 있습니다.
C++를 어떻게 알고리즘을 푸는데 활용하는지 알아보겠습니다.
STL 헤더
C++의 장점은 유용한 STL을 이용할 수 있다는 점입니다.
이 STL을 이용하려면, 물론 헤더를 include 해야합니다.
iostream, vector, string, algorithm 등 유용한 것이 많은데, 이를 GCC계열 컴파일러에서는 하나로 모아둔 헤더가 존재합니다.
#include <bits/stdc++.h>대부분의 경우에 위와 같이 한줄만 입력하면 해결이 됩니다.
그러나 환경에 따라 개별적으로 헤더파일을 추가해야하는 경우도 있습니다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
...한편, stl을 사용하기 위해서 std라는 namespace를 계속 사용해주어야하는데 이를 생략하려면 다음 한줄을 추가해주면 됩니다.
using namespace std;I/O 속도개선
입출력에 걸리는 시간을 줄이는 방법이 존재합니다.
먼저 sync_with_stdio를 해제해주면, cin과 cout의 속도가 크게 향상됩니다.
std::ios_base::sync_with_stdio(false);대신 scanf/printf를 cin/cout 과 같이 쓰지 못하게 됩니다.
정확히는 쓰지 못한다기 보다는 순서가 꼬이는 오류가 발생할 수 있고, 또 멀티쓰레드 환경에서는 사용하지 않는 것이 좋다고 합니다.
cout 출력버퍼를 cin 동작과 묶어주는 것을 해제하면 속도가 조금 빨라집니다.
보통 테스트케이스가 많은 경우에 효과가 높아집니다.
std::cin.tie(NULL);다만 부분점수를 받을 수 있는 경우에는 출력버퍼를 수동으로 비워줘야 합니다.
그럴 때는 줄바꿈을 endl 로 바꿔주면 됩니다.
이는 SCPC대회 공식 권장사항이기도 합니다.
std::cout << endl;지금까지 내용을 요약하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
ios_base::sync_with_stdio(false);
cin.tie(NULL);입출력
cin으로 받는 입력은 굉장히 편리합니다.
int N, M, K; cin >> N >> M >> K;한줄을 문자열로 받을 수도 있습니다.
stirng S; getline(cin, S);cout을 통한 출력도 편리합니다.
int N = 37; cout << N << "\n";소수를 출력할 때, 자리수를 지정해줄 수 있습니다.
double d = 1.234567; cout.precision(3); cout << fixed; cout << d;출력 글자수를 맞춰줄 수도 있습니다.
cout.width(n);출력 글자수를 맞출 때, 빈칸을 채울 문자를 정할 수 있습니다.
cout.fill('*');
벡터
C++에서는 배열을 더 쉽고 유용하게 사용할 수 있게 해주는 vector 컨테이너가 존재합니다.
vector 선언방법
담을 변수의 자료형을 꺽쇠안에 입력합니다.
vector<int> v;크기를 지정하여 만들어 줄 수도 있습니다.
vector<int> v(10);배열과 달리 변수로 크기를 설정해도 괜찮습니다.
int size = 10; vector<int> v(size);초기값을 정해줄 수도 있습니다.
int size = 10; vector<int> v(size, 3);이차원 벡터를 만들 수도 있습니다.
vector<vector<int>> v;이차원 벡터의 크기 지정은 좀 번거로울 수 있습니다.
vector<vector<int>> v(10, vector<int>(5, 3));벡터에 값을 추가해줄 수 있습니다.
v.push_back(37);벡터의 크기를 확인할 수 있습니다.
v.size();벡터를 초기화 해줄 수 있습니다.
v.clear();벡터 크기를 재지정해줄 수 있습니다.
v.resize(37);벡터의 예상크기를 지정하면 효율이 좋아집니다.
v.reserve(37);
resize 함수의 경우에는 기존값을 초기화하지 않기 때문에, 초기화를 같이 해주어야 하는 경우에는 clear 를 먼저 사용해야합니다.
또한 위와 같은 이유로 이차원 벡터의 크기를 조정할 때, clear없이 resize하는 경우 런타임에러가 발생할 수 있습니다.
사례
vector 활용
오름차순 정렬
sort(v.begin(), v.end());내림차순 정렬
sort(v.begin(), v.end(), greater<int>());사용자 설정 정렬
bool cmp(int a, int b) return a < b; sort(v.begin(), v.end(), cmp);정렬된 경우 이분탐색 (크거나 같은 값)
lower_bound(v.begin(), v.end(), 37);정렬된 경우 이분탐색 (더 큰 값)
upper_bound(v.begin(), v.end(), 37);순차탐색 (같은 값)
find(v.begin(), v.end(), 37);이분탐색에서 찾는 값이 없는 경우
if(lower_bound(v.begin(), v.end(), 37) == v.end()) { // no such value }조합 탐색 (사전순)
do { // } while(next_permutation(v.begin(), v.end());
문자열
새로운 문자열
stirng str;크기 확인
str.size();문자열 찾기
str.find("asdf");문자열을 찾을 수 없는 경우
if(str.find("asdf") == string::npos) { // cant find }
맵 / 셋
새로운 map 과 set 생성
map<string, int> m; set<int> s;값 추가
m["asdf"] = 1234; s.insert(1234);값 존재 확인
m.count("asdf"); s.count(1234);맵에서 값 확인
m["asdf"];값 제거
m.erase("asdf"); s.erase(1234);
주의할 점은 map에서 대괄호로 값을 확인하려고 하면, 없던 값이 새로 생길 수 있습니다.
이런 경우 메모리와 속도 측면에서 손해가 발생하며 오류 발생의 가능성이 있으니, 값의 존재만을 확인한다면 map에서도 count를 사용해야 합니다.
큐 / 우선순위큐
큐 생성 / 우선순위큐(내림차순) 생성
queue<int> q; priority_queue<int> pq;푸시
q.push(37); pq.push(37);팝
q.pop(); pq.pop();값 확인 - 주의
q.front(); pq.top();우선순위큐를 오름차순으로 만들기
priority_queue<int, vector<int>, greater<int>> pq;우선순위큐를 사용자 설정 기준으로
struct cmp{bool operator()(int a, int b){return a < b;}} priority_queue<int, vector<int>, cmp> pq;
한편 스택을 이용한다면 stack 컨테이너도 존재하지만, vector를 사용해도 문제되지 않습니다.
그 외
최대값
max(a, b);최소값
min(a, b);문자열을 정수형으로
stoi("37");정수형을 문자열로
to_string(37);문자열을 여러개의 정수형으로
int A, B, C; stringstream ss("123 456 789"); ss >> A >> B >> C;
