알고리즘 트레이닝 - 안티 라크소넨 책에서…
long long
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
long long x = 123456789123456789LL;
// 아래 코드는 버그가 있다
int a = 123456789;
long long b = a*a;
cout << b << "\n"; //-1757895751
// g++ 컴파일러가 지원하는 자료형
__int128_t c;
}
|
기본 템플릿
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
// 한줄입력
string s;
getline(cin,s);
// 데이터의 양을 사전에 알수 없는 경우
while(cin>>x){
}
// 파일을 입출력에 사용하는 경우
// 평소처럼 표준 스트림을 사용하는 코드 작성후
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
|
modulo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
// 결과에 mod 한것과, 각 항에 mod후 연산한것 결과가 같다
// (a+b)mod m = (a mod m+b mod m) mod m
// (a-b)mod m = (a mod m-b mod m) mod m
// (a*b)mod m = (a mod m*b mod m) mod m
// n! mod m
// long long x = 1;
// long long m = 11;
// for(int i=1;i<=n;i++){
// x = (x%i)%m;
// }
// cout << x << "\n";
// 음수의 mod, 결과가 음수라면 +m
// x = x%m;
// if(x<0) x+= m;
// 부동소수점 실수
// 64bit-double, 80bit-long double
double x2 = 0.3;
printf("%.9f\n",x2);
double x = 0.3*3 + 0.1;
printf("%.20f\n",x); //0.99999999999999988898
//부동소수점 실수를 == 로 비교시 위험
double a = 0.1;
double b = 0.1;
if(abs(a-b)<1e-9){
cout << "abs(a-b)<1e-9 true??";
}
}
|
typedef
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(int i=a;i<=b;i++)
int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
// typedef 로 코드 짧게 만들기
ll a = 123456789;
ll b = 123456789;
cout << a*b << "\n";
// 코드 짧게 만들기
vector<pair<int,int>> v1;
v1.push_back(make_pair(1,2));
v1.push_back(make_pair(3,4));
int d = v1[0].first + v1[1].second;
cout << d << "\n";
vpi v2;
v2.PB(MP(1,2));
v2.PB(MP(3,4));
int d2 = v2[0].F + v2[1].S;
cout << d2 <<"\n";
//for문 단축
REP(i,1,5){
cout << i;
}
return 0;
}
|
recursion
subset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> subset;
void search(int k){
if(k==n+1){
//부분집합을 처리한다
for(int x:subset){
cout << x << " ";
}
cout << "\n";
} else {
//k를 부분집합에 포함시킨다
subset.push_back(k);
search(k+1);
subset.pop_back();
//k를 부분집합에 포함시키지 않는다
search(k+1);
}
}
int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
// 1부터 3까지 수로 부분집합
n=3;
search(1);
return 0;
}
|
permutation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int n = 3;
vector<int> permutation;
bool chosen [n+1];
void search(){
if(permutation.size()==n){
//순열을 처리한다
for(auto &e:permutation) cout << e << " ";
cout << "\n";
} else {
for(int i=1;i<=n;i++){
if (chosen[i]) continue;
chosen[i] = true;
permutation.push_back(i);
search();
chosen[i] = false;
permutation.pop_back();
}
}
}
int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
search();
return 0;
}
|
backtracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<iostream>
#include<bits/stdc++.h>
using namespace std;
void search(int y){
if (y==n) {
count++;
return;
}
for (int x=0;x<n;x++){
if (col[x] || diag1[x+y] || diag2[x-y+n-1]) continue;
col[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
search (y+1);
col[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
}
}
int main(){
return 0;
}
|
bit operation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void bit_mask(int x){
for(int k=31;k>=0;k--){
if (x&(1<<k)) cout << "1";
else cout << "0";
}
}
int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
bit_mask(14);
int x = 5328;
cout << __builtin_clz(x) << "\n";
return 0;
}
|
1«k 는 k번째 위치에만 비트 1이 있고 나머지 위치에는 비트 0이 있는 정수이다. 특정한 비트 하나에 접근할 수 있게 되는것.
x|(1«k)는 정수 x의 k번째 비트를 1로 바꾸는 것
x&~(1«k)는 k번째 비트를 0으로 바꾸는 것
x^(1«k)는 k번째 비트를 뒤집는것
x&(x-1)은 가장 오른쪽의 비트 1을 0으로 바꾸는것
x&-x는 정수 x의 모든 비트를 0으로 바꾸되, 비트 1중 제일 오른쪽 것만 하나 남기는 공식
x|(x-1)은 마지막 비트 1 다음에 오는 모든 비트를 뒤집는 공식
주의점은 1«k 가 항상 int형이다. long long형 비트마스크를 사용 하는 간단한 방법은 1LL«k
x&-x는 정수 x의 모든 비트를 0으로 바꾸되, 비트 1중 제일 오른쪽 것만 하나 남기는 공식