/*
* Source : https://www.math.wustl.edu/~victor/mfmm/compaa/gcd.c
*/
#include <stdio.h>
/* Standard C Function: Greatest Common Divisor */
int gcd(int a, int b)
{
int c;
while (a != 0) {
c = a; a = b % a; b = c;
}
return b;
}
/* Recursive Standard C Function: Greatest Common Divisor */
int gcdr(int a, int b)
{
if (a == 0) return b;
return gcdr(b%a, a);
}
/* Recursive one line implementation
int gcd(int a,int b) {
return a == 0 ? b : gcd(b % a, a);
}
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}
*/
int main(void)
{
int a, b, c;
a = 299792458;
b = 6447287;
c = 256964964;
printf("a=%d, b=%d, c=%d\n", a, b, c);
printf("gcd(a,b)=gcd(%d,%d)=%d\n", a, b, gcd(a, b));
printf("gcd(a,b)=gcdr(%d,%d)=%d\n", a, b, gcdr(a, b));
printf("gcd(a,c)=gcd(%d,%d)=%d\n", a, c, gcd(a, c));
printf("gcd(a,c)=gcdr(%d,%d)=%d\n", a, c, gcdr(a, c));
printf("gcd(c,b)=gcd(%d,%d)=%d\n", c, b, gcd(c, b));
printf("gcd(c,b)=gcdr(%d,%d)=%d\n", c, b, gcdr(c, b));
printf("gcd(a,b,c)=gcd(%d,gcd(%d,%d))=%d\n", a, b, c, gcd(a, gcd(b, c)));
printf("gcd(a,b,c)=gcdr(%d,gcdr(%d,%d))=%d\n", a, b, c, gcdr(a, gcdr(b, c)));
return 0;
}
view raw gcd.c hosted with ❤ by GitHub
저작자표시

'알고리즘 & Problem Solving > 레퍼런스코드' 카테고리의 다른 글

[레퍼런스코드] 에라토스테네스의 체  (0) 2020.05.08
[레퍼런스코드] Disjoint Set 코드(DSU / Union-Find 자료구조)  (0) 2020.01.25
[레퍼런스코드] 머지소트(병합정렬)  (0) 2019.10.30
#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long ll;
#define MAXN 10000
int min_factor[MAXN]; //약수 중 가장 작은 녀석
int main() {
//에라토스테네스의 채
//0,1 빼고 모두 소수라고 가정하고 시작
min_factor[0] = -1;
for (int i = 2; i < MAXN; i++) {
min_factor[i] = i;
}
for (int i = 2; i*i < MAXN; i++) {
if (min_factor[i] == i) { // i가 소수이면
//i^2 부터 +i씩 한 값들은 모두 합성수에 해당됨
for (int j = i * i; j < MAXN; j += i) {
if (min_factor[j] == j) {
min_factor[j] = i;
}
}
}
}
//소수들 출력
for (int i = 2; i < MAXN; i++) {
if (min_factor[i] == i) {
cout << i << endl;
}
}
}
view raw sieve_eratosthenes.cc hosted with ❤ by GitHub
저작자표시

'알고리즘 & Problem Solving > 레퍼런스코드' 카테고리의 다른 글

[레퍼런스코드] 유클리드 호제법 최대공약수 구하기(GCD)  (2) 2020.05.15
[레퍼런스코드] Disjoint Set 코드(DSU / Union-Find 자료구조)  (0) 2020.01.25
[레퍼런스코드] 머지소트(병합정렬)  (0) 2019.10.30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define MAXN 50020
// disjoint set (DSU)
int parent[MAXN];
// rank를 뜻함
int depth[MAXN];
//find 함수
int root(int a) {
int p = a;
while (p != parent[p])
p = parent[p];
parent[a] = p;
return p;
}
//같은 set에 포함되어있는지를 리턴
bool same(int a, int b) {
return root(a) == root(b);
}
//union 함수
void unite(int a, int b) {
a = root(a);
b = root(b);
if (a == b) return;
if (depth[a] < depth[b]) {
parent[a] = b;
}
else {
parent[b] = a;
if (depth[a] == depth[b])
depth[b]++;
}
}
void init(int N) {
for (int i = 0; i < N; i++) {
parent[i] = i;
depth[i] = 0;
}
}
int main() {
int n;
scanf("%d", &n);
init(n);
return 0;
}
view raw dsu.cc hosted with ❤ by GitHub
저작자표시

'알고리즘 & Problem Solving > 레퍼런스코드' 카테고리의 다른 글

[레퍼런스코드] 유클리드 호제법 최대공약수 구하기(GCD)  (2) 2020.05.15
[레퍼런스코드] 에라토스테네스의 체  (0) 2020.05.08
[레퍼런스코드] 머지소트(병합정렬)  (0) 2019.10.30

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define MAXN 1000006
int arr[MAXN];
int tmp[MAXN];
void merge_sort(int arr[], int start, int end) {
int mid = (start + end) / 2;
if (start < mid) {
merge_sort(arr, start, mid);
merge_sort(arr, mid, end);
int p = start, q = mid, r= start;
while (p < mid && q < end) {
if (arr[p] < arr[q]) {
tmp[r++] = arr[p++];
}
else {
tmp[r++] = arr[q++];
}
}
while (p < mid) {
tmp[r++] = arr[p++];
}
while (q < end) {
tmp[r++] = arr[q++];
}
for (int i = start; i < end; i++) {
arr[i] = tmp[i];
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
merge_sort(arr, 0, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << endl;
}
}
view raw merge_sort.cc hosted with ❤ by GitHub

https://www.acmicpc.net/problem/2751

 

2751번: 수 정렬하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

위 문제의 정답코드이기도 합니다.

 

코드 복사를 하려면 gist의 우측 하단의 view-raw를 누른 뒤 복사하시면 됩니다.

'알고리즘 & Problem Solving > 레퍼런스코드' 카테고리의 다른 글

[레퍼런스코드] 유클리드 호제법 최대공약수 구하기(GCD)  (2) 2020.05.15
[레퍼런스코드] 에라토스테네스의 체  (0) 2020.05.08
[레퍼런스코드] Disjoint Set 코드(DSU / Union-Find 자료구조)  (0) 2020.01.25

+ Recent posts

티스토리툴바