수학 알고리즘 - 기초(1)

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

2609번: 최대공약수와 최소공배수

유클리드 호재법 알고리즘이다.

 

최대공약수 GCD(Greatest Common Divisor)

최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

ex) 72 와 30의 최대공약수는 6이다.

 

 

최소공배수 LCM(Least Common Multiple)

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

최소공배수 = 두 자연수의 곱 / 최대공약수

ex) 72 와 30의 최소공배수는 360이다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
using namespace std;

int gcd(int a, int b)
{
	if (a % b == 0)
		return b;
	else
		return gcd(b, a % b);
}

int main(void)
{
	freopen("input.txt", "r", stdin);
	int a, b;
	scanf("%d %d", &a, &b);
	int ans = gcd(a, b);
	printf("%d\n%d\n", ans, a*b/ans);
}

 

 

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

1934번: 최소공배수

동일한 문제이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
using namespace std;

int gcd(int a, int b)
{
	if (a % b == 0)
		return b;
	else
		return gcd(b, a % b);
}

int main(void)
{
	freopen("input.txt", "r", stdin);
	int c;
	scanf("%d\n", &c);
	while (c--)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		int ans = gcd(a, b);
		printf("%d\n", a * b / ans);
	}
	
}

 

 

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

1978번: 소수 찾기

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

int find_sosu(int d)
{
	if (d <= 1) return false;
	for (int i = 2; i <= sqrt(d); ++i)
	{
		if (d % i == 0)
		{
			return false;
		}
	}
	return true;
}

int main(void)
{
	freopen("input.txt", "r", stdin);
	int c;
	scanf("%d\n", &c);
	int ans = 0;
	while (c--)
	{
		int d;
		scanf("%d", &d);
		ans += find_sosu(d) ? 1 : 0;
	}
	printf("%d\n", ans);
	
}

소수를 푸는 가장 쉬운 방법은 루트보다 작을때까지의 값들을 나누어 보는 것이다.

입력이 적다면 쓸 수 있는 간단한 알고리즘이지만 이거 생각보다 속도가 매우 느리다.

 

그래서 뒤에서 골드바흐의 추측이 나오게 된다. 에라토스테네스의 채라는 풀이 인데 방법이 두 가지가 있었다.

 

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

1929번: 소수 구하기

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

int find_sosu(int d)
{
	if (d <= 1) return false;
	for (int i = 2; i <= sqrt(d); ++i)
	{
		if (d % i == 0)
		{
			return false;
		}
	}
	return true;
}

int main(void)
{
	//freopen("input.txt", "r", stdin);
	
	int a, b;
	scanf("%d %d", &a, &b);
	for (int i = a; i <= b; ++i)
	{
		if (find_sosu(i))
			printf("%d\n", i);
		else
			continue;
	}
	return 0;
}

 

 

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

6588번: 골드바흐의 추측

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int find_sosu(int d)
{
	if (d <= 1) return false;
	for (int i = 2; i <= sqrt(d); ++i)
	{
		if (d % i == 0)
		{
			return false;
		}
	}
	return true;
}

int main(void)
{
	freopen("input.txt", "r", stdin);
	
	int d = 0;
	
	char map[1000001] = { 0 };
	
	for (int i = 2; i * i <= 1000000; i++)
	{
		if (map[i] == 0)
		{
			for (int j = i + i; j <= 1000000; j += i)
			{
				map[j] = 1;
			}
		}
	}
	vector<int> prime;
	for (int i = 2; i <= 1000000; i++)
	{
		if(map[i] == 0)
			prime.push_back(i);
	}
	while (scanf("%d", &d))
	{
		if (d == 0) break;
		for (int i = 0; prime[i] < d; i++)
		{
			int b = d - prime[i];
			if (find_sosu(b))
			{
				printf("%d = %d + %d\n", d, prime[i], b);
				break;
			}
		}
	}
	return 0;
}

위와같이 시작 2부터해서 그거의 배수를 미리 배열에 저장해 놓으면 소수만 남게 된다는 원리인데

이게 메모리를 많이 차지해서 나도 에러를 몇 번 먹고 map을 char로 선언하게 되었다;;

 

사실 아래 짓거리 해도 문제가 풀리기는 한다;;

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

int find_sosu(int d)
{
	if (d <= 1) return false;
	for (int i = 2; i <= sqrt(d); ++i)
	{
		if (d % i == 0)
		{
			return false;
		}
	}
	return true;
}

int main(void)
{
	//freopen("input.txt", "r", stdin);
	
	int d = 0;
	while (scanf("%d", &d))
	{
		if (d == 0) break;
		for (int i = 1; i < d / 2; i++)
		{
			int a = i * 2 + 1;
			int b = d - a;
			if (find_sosu(a) && find_sosu(b))
			{
				printf("%d = %d + %d\n", d, a, b);
				break;
			}
		}
	}
	return 0;
}

그냥 소수는 2를 제외하고 홀수이기 때문에 그거의 배수로 계산을 때려버리면 결과가 빠르게 나온다.

 

심지어 속도 차이도 난다;;

 

 

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

10872번: 팩토리얼

팩토리얼 계열의 문제이다.

그냥 점화식으로 풀면된다.

 

맞다. 수학에서부터 점화식이 나온다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int facto(int n)
{
	if (n <= 1) return 1;
	return n * facto(n - 1);
}
int main(void)
{
	//freopen("input.txt", "r", stdin);
		
	int d = 0;
	scanf("%d\n", &d);
	printf("%d\n", facto(d));
}

 

 

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

1676번: 팩토리얼 0의 개수

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main(void)
{
	//freopen("input.txt", "r", stdin);
		
	int d = 0;
	scanf("%d\n", &d);
	
	int ans = 0;
	for (int i = 5; i <= d; i *= 5)
	{
		ans += d / i;
	}
	printf("%d\n", ans);
	return 0;
}

이건 팩토리얼과 1도 관계가 없어보일 수도 있지만

팩토리얼의 특성을 가지고 푸는 문제이다.

https://torbjorn.tistory.com/247

[백준][C++] 1676: 팩토리얼 0의 개수

대충 100! 을 구한다고 하더라도 5로 나누면 5와 관련된 숫자가 나오는 경우는 20회 정도이다.

25로 나누면 4회

 

그래서 100! 에서 0이 나오는 경우는 24회인데

 

실재로도 24회이다.

 

그래서 5의 제곱승으로 나누어주면된다. 이건 트릭치한것이기 때문에 이렇게 풀 수 있다고 인지하자

 

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

2004번: 조합 0의 개수

사실 이것도 비슷한데 nCr을 해주면 n!/(r! * (n-r)!) 으로 계산하게 된다.

그래서

n!

r!

(n-r)!

에서 5의 제곱수들로 나눈 것을 모두 합하면 답이 나온다.

 

여기서 주의점은 입력값이 int를 넘어가기 때문에 자료형 선정에 주의를 요한다는 점과

2와 5로 나눈 것 중 어느 것이 더 적은 수인지 모르기 때문에 두 가지를 모두 비교해주어야 한다는 점이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int div_n(long long n, int div)
{
	int ans = 0;
	for (long long i = div; i <= n; i *= div)
	{
		ans += n / i;
	}
	return ans;
}
int main(void)
{
	//freopen("input.txt", "r", stdin);
		
	long long a,b = 0;
	scanf("%lld %lld\n", &a,&b);
	long long div_five = div_n(a,5) - div_n(b,5) - div_n(a - b,5);
	long long div_two = div_n(a, 2) - div_n(b, 2) - div_n(a - b, 2);

	printf("%d\n", min(div_five,div_two));
	return 0;
}

 

 

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

9613번: GCD 합

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int gcd(int a, int b)
{
	if (a % b == 0) return b;
	return gcd(b, a % b);
}
int main(void)
{
	//freopen("input.txt", "r", stdin);
	
	int t = 0;
	scanf("%d\n", &t);
	while (t--)
	{
		int c = 0;
		scanf("%d", &c);
		vector<int> d;
		for (int i = 0; i < c; ++i)
		{
			int tmp = 0;
			scanf("%d", &tmp);
			d.push_back(tmp);
		}

		long long ans = 0;
		for (int i = 0; i < c; ++i)
		{
			for (int j = i + 1; j < c; ++j)
			{
				ans += gcd(d[i], d[j]);
			}
		}
		printf("%lld\n", ans);
	}
	
	return 0;
}

그냥 기존에 연습한거 잘 활용해주면 된다.

 

 

 

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

17087번: 숨바꼭질 6

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

long long gcd(long long a, long long b)
{
	if (a % b == 0) return b;
	return gcd(b, a % b);
}
int main(void)
{
	//freopen("input.txt", "r", stdin);
	
	long long n, s;
	scanf("%lld %lld\n", &n, &s);
	vector<long long> d;
	long long cnt = n;
	while (cnt--)
	{
		long long tmp;
		scanf("%lld", &tmp);
		d.push_back(abs(s-tmp));
	}

	long long ans = d[0];
	for (int i = 1; i < n; ++i)
	{
		ans = gcd(ans, d[i]);
	}
	printf("%d\n", ans);
	return 0;
}

이것도 비슷하게 gcd를 잘 응용해주라는 문제이다.

 

 

 

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

1373번: 2진수 8진수

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main(void)
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string d;
	cin >> d;
	while (d.length() % 3 != 0)
	{
		d = '0' + d;
	}
	for (int i = 0; i < d.length(); i += 3)
	{
		int ans = (d[i] - '0') * 4 + (d[i + 1] - '0') * 2 + (d[i + 2] - '0') * 1;
		cout << ans;
	}
	return 0;
}

진법변환문제인데 여기에서부터 주의할 점은 string을 사용할 경우 scanf를 사용 못한다. 그래서 cin을 써야하는데 cin을 쓴다면 ios_base와 cin.tie, cout.tie 문법을 써줄 수 있어서 속도를 조금 더 높히었다.

 

알고리즘은 단순하게 3자리수씩 끊어서 생각하면된다.

https://nanyoungkim.tistory.com/174

[C++] 백준 1373번 - 2진수 8진수 (문자열)

이 분 블로그를 참고하였다.

 

 

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

1212번: 8진수 2진수

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
using namespace std;

int main(void)
{
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string d;
	cin >> d;
	string eight[8] = { "000","001","010","011","100","101","110","111" };
	for (int i = 0; i < d.length(); ++i)
	{
		int tmp = d[i] - '0';
		if (i == 0) cout << stoi(eight[tmp]);
		else cout << eight[tmp];
	}
}

 

https://velog.io/@ap3334/%EB%B0%B1%EC%A4%80-C-1212.-8%EC%A7%84%EC%88%98-2%EC%A7%84%EC%88%98

[백준 C++] 1212. 8진수 2진수

https://velog.io/@youhyeoneee/%EB%B0%B1%EC%A4%80-2089%EB%B2%88-2%EC%A7%84%EC%88%98

[백준] 2089번: -2진수

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int N;

void trans(int n){

    if (n == 0)
        return;

    // 경우 1. 2로 나눠지는 경우
    if (n % 2 == 0){
        trans(-(n/2));
        cout << 0;
    }
    else{
        // 경우 2-1. 2로 나눠지지 않는 경우 + 양수 인 경우 
        if(n > 0) 
            trans(-(n / 2)); 
        // 경우 2-2. 2로 나눠지지 않는 경우 + 음수 인 경우 
        else 
            trans((-n + 1) / 2);
        cout << 1;
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    if (N == 0)
        cout << 0;
    else   
        trans(N);
    
    cout << '\n';

    return 0;
}