알고리즘 문제 작성 가이드 및 템플릿
자주사용하는 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
typedef long long ll;
struct Point{
ll X ,Y;
Point operator - (const Point &p){return {X-p.X, Y - p.Y};}
Point operator + (const Point &p){ return {X+p.X, Y+p.Y};}
bool operator <(const Point &p){return tie(X,Y) < tie(p.X, p.Y);}
bool operator >(const Point &p){return tie(X,Y) > tie(p.X, p.Y);}
bool operator == (const Point &p){return tie(X,Y) == tie(p.X, p.Y);}
bool operator >= (const Point &p){return tie(X,Y) >= tie(p.X, p.Y);}
bool operator <= (const Point &p){return tie(X,Y) <= tie(p.X, p.Y);}
};
ll cross(const Point &p, const Point &q){
return p.X*q.Y - q.X*p.Y;
}
ll ccw(Point p, Point q, Point r){
ll c = cross(q-p, r-q);
if(c > 0) return 1;
else if(c == 0) return c;
else return -1;
}
struct Line{
Point p1,p2;
Line(Point p1, Point p2) : p1(p1), p2(p2) {}
};
bool line_cross(Line L1, Line L2){
auto [a,b] = L1;
auto [c,d] = L2;
ll ab = ccw(a,b,c) * ccw(a,b,d);
ll cd = ccw(c,d,a) * ccw(c,d,b);
if(ab == 0 && cd == 0){
if(a > b) swap(a,b);
if(c> d) swap (c,d);
return b >= c && a <= d;
}
return ab <= 0 && cd <= 0;
}
Line _ext(Point p1, Point p2,ll l, ll r){
auto [x1,y1] = p1;
auto [x2,y2] = p2;
if(x1 == x2) return { {x1, l} , {x1,r} };
else if(y1 == y2) return { {l,y1} , {r,y1} };
else{
ll d;
if((y2-y1) == (x2-x1)) d= 1;
else d = -1;
return { {l,d*(l-x1)+y1} , {r,d*(r-x1)+y1} };
}
}
행렬 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;