알고리즘 문제 작성 가이드 및 템플릿
자주사용하는 Templete
기본적으로 많이 사용하는 PS 템플릿
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef tuple<int,int,int> iii;
기하 Templete
using Point = pair<int64_t, int64_t>;
#define X first
#define Y second
Point operator - (const Point &p, const Point &q){
return {p.X-q.X, p.Y-q.Y};
}
Point operator + (const Point &p, const Point &q){
return {p.X+q.X, p.Y+q.Y};
}
bool cmp(const Point&p, const Point &q){
if(p.Y != q.Y) return p.Y > q.Y;
return p.X < q.X;
}
int64_t cross(const Point &p, const Point &q){
return p.X*q.Y - q.X*p.Y;
}
int64_t ccw(Point p, Point q, Point r){
int64_t c = cross(q-p, r-q);
if(c > 0) return 1;
else if(c == 0) return c;
else return -1;
}
행렬 TEmplete
struct matrix {
vector<vector<int>> M;
matrix(int n = 0) : M(n, vector<int>(n)) {}
vector<int>& operator [] (int i) { return M[i]; }
matrix& operator += (matrix m) { return *this = *this + m; }
matrix& operator *= (matrix m) { return *this = *this * m; }
friend matrix operator + (matrix a, matrix b) {
int n = a.M.size(); matrix ret(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
ret[i][j] = (a[i][j] + b[i][j]) % 1000;
}
return ret;
}
friend matrix operator * (matrix a, matrix b) {
int n = a.M.size(); matrix ret(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) ret[i][j] += a[i][k] * b[k][j];
ret[i][j] %= 1000;
}
return ret;
}
};
FASTIO
cin, cout 는 속도가 느리기 때문에 다음을 main 안에 넣어놓고 사용한다.
cin.tie(0)->sync_with_stdio(0);
자주 사용되는 입출력 루틴
// 테스트케이스가 있는 경우
int TC; cin >> TC;
while(TC--){
//program
}
// 입력의 끝부분에 특정 값이 주어지는 경우
int a,b;
//만약 a == b == 0 인경우 프로그램 종료
while(scanf("%d %d",&a,&b), (a || b)){
//program
}
비트 연산
정수인 수들을 다루다보면 비트로 연산하는게 코드가 훨씬 간결하다.
// 짝 홀수 판별
N&1 --> even : 0 , odd : 1
// K+1 번째 자리수 (2진법)
n >> k&1
// n은 2의 거듭제곱수
!(n&(n-1))
// 나누기 2
n >> 1
비트를 사용하여 집합으로 나타내기
bit를 이용하여 집합을 표현한다면 다음처럼 사용할 수 있음
집합의 j 번째의 원소를 켜기 - Or 연산 사용
S |= (1 << j)
집합의 j 원소가 켜져 있는지 확인하려면 And 연산을 사용한다.
T = S & (1 << j)
if( T == 0) j 번쨰 원소는 꺼져있음
집합의 j 번쨰 원소 끄기 - And 사용
S &= ~(1 << j)
집합의 j 번쨰 원소 반전 - XOR 사용
S &= ~(1 << j)
켜져 있는 최하위 비트를 구하기(오른쪽)
T = (S & (-S) )
크기가 n 인 집합의 모든 비트 켜기
S = (1 << n) -1
어떤 수가 0부터 9까지 모두 사용되었는지 확인
while(tmp) { T |= 1 >> (tmp % 10); tmp /= 10;}
if(T == (1 << 10) -1) return true;