백준 알고리즘 기초 : 수학

2609. (최대공약수와 최소공배수) 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

#include<iostream>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int a, b;
	cin >> a >> b;
	int minVal = 1;
	int n = min(a, b);
	while (n > 1) {
		if (a % n == 0 && b % n == 0) {
			minVal *= n;
			a /= n;
			b /= n;
			n = min(a, b);
		}
		n--;
	}
	cout << minVal << "\n" << minVal * a * b;
}

나는 실제 최소공배수 구하는 것처럼 구했는데 더 쉽게 푸는 방법이 있었다.

 

#include<iostream>
#include <algorithm>
using namespace std;
int gcd(int x, int y) {
	int temp = x % y;
	while (temp) {
		x = y;
		y = temp;
		temp = x % y;
	}
	return y;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b) << "\n" << (a * b) / gcd(a, b);
}

유클리드 호제법을 사용하여 푸는 방법이다.

https://sectumsempra.tistory.com/77

[백준2609]-최대공약수와 최소공배수(C++)/유클리드 호제법

유클리드 호제법은 위 티스토리에 자세히 나와있다. 

 

 

1934. (최소공배수) 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

#include<iostream>
using namespace std;
int gcd(int x, int y) {
	int z = x % y;
	while (z) {
		x = y;
		y = z;
		z = x % y;
	}
	return y;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int t, a, b;
	cin >> t;
	while (t--) {
		cin >> a >> b;
		cout << a * b / gcd(a, b) << '\n';
	}
	return 0;
}

유클리드 호제법을 사용하면 되는 간단한 문제이다.

#include<algorithm>
int gcd = __gcd(a, b);

c++ stl의 __gcd() 함수를 이용해서 최대공약수를 구할 수 있다.

 

 

 

1978. (소수 찾기) 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

#include<iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, x, count = 0;
	cin >> n;
	while (n--) {
		cin >> x;
		int temp = 0;
		for (int i = 1; i <= x; i++)
		{
			if (x % i == 0)
				temp++;
		}
		if (temp == 2) {
			count++;
		}
	}
	cout << count;
	return 0;
}

백준 단계 9 : 약수, 배수와 소수에서 다룬 문제이다.

 

 

 

1929. (소수 구하기)  M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

- 에라토스테네스의 체

#include<iostream>
#include<vector>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int m, n;
	cin >> m >> n;
	vector<bool> v(n + 1, 1);
	v[0] = 0;
	v[1] = 0;
	for (int i = 2; i < n + 1; i++)
	{
		if (v[i] == 0)
			continue;
		for (int j = i * 2; j < n + 1; j += i)
		{
			v[j] = 0;
		}
	}

	for (int i = m; i <= n; i++)
	{
		if (v[i])
			cout << i << '\n';
	}
}

1978처럼 풀면 안되는 문제이다.1978처럼 O(n^2)이 나와서 시간초과가 된다. 에라토스테네스의 체라는 방식을 써야 한다.

에라토스테네스의 시간복잡도는 O(nlog(logn))이다. 

시간은 약 16ms가 나왔다.

 

 

- 소수 판별법

#include<iostream>
#include<vector>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int m, n;
	cin >> m >> n;
	if (m == 1)
		m++;
	for (int i = m; i <= n; i++)
	{
		bool flag = 1;
		for (int j = 2; j * j <= i; j++)
		{
			if (i % j == 0) {
				flag = 0;
				break;
			}
		}
		if (flag)
			cout << i << '\n';
	}
	
}

16의 약수는 1, 2, 4, 8, 16이 된다. 여기서 16의 제곱근인 4를 기준으로 1*16, 2*8처럼 곱하는 수가 대칭이 되기 때문에 제곱근까지만 검사하면 된다. 그럼 시작복잡도가 O( √ n)이 된다.

시간은 약 188ms가 나왔다.

 

 

 

6588. (골드바흐의 추측) 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> findP(int n) {
	vector<bool> temp(n + 1, 1);
	for (int i = 3; i < n + 1; i++)
	{
		for (int j = i * 2; j < n + 1; j += i)
		{
			temp[j] = 0;
		}
	}
	vector<int> prime;
	for (int i = 3; i < n + 1; i++)
	{
		if (temp[i])
			prime.push_back(i);

	}
	return prime;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> prime = findP(1000000);

	while (n != 0) {
		int index = lower_bound(prime.begin(), prime.end(), n) - prime.begin() - 1;

		bool flag = 0;
		for (int i = 0; prime[index - i] >= n / 2; i++)
		{
			if ((n - prime[index - i]) % 2 == 1) {
				if (*lower_bound(prime.begin(), prime.end(), n - prime[index - i]) == n - prime[index - i]) {
					cout << n << " = " << n - prime[index - i] << " + " << prime[index - i] << "\n";
					flag = 1;
					break;
				}
			}
		}
		if (!flag)
			cout << "Goldbach's conjecture is wrong.\n";
		cin >> n;
	}

}

나는 조금 어렵게 푼 거 같아서 다른 사람 코드를 참조하는 걸 추천한다.

 

https://morm.tistory.com/358

백준 C++ 6588번 문제 - 골드바흐의 추측

https://minyeok2ee.gitlab.io/boj/boj-6588/

[BOJ][C++] 백준 6588번 골드바흐의 추측

 

 

 

10872. (팩토리얼)  0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

#include<iostream>
using namespace std; 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, fac = 1;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		fac *= i;
	}
	cout << fac;
    return 0;
}

팩토리얼을 알면 풀 수 있는 쉬운 문제였다.

 

 

 

1676. (팩토리얼 0의 개수) N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

#include<iostream>
using namespace std; 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, count = 0;
	cin >> n;
	for (int i = 5; i <= n; i*=5)
	{
		count += n / i; 
	}
	cout << count << "\n";
}

5의 개수를 센다면 0의 개수를 알 수 있을 것이다. 0이 만들어질라면 10이 만들어져야 하는데, 2의 개수보다 5의 개수가 적기 때문에 5의 개수만 세면 된다. (원래는 2의 개수랑 비교해서 더 적게 있는 값을 선택하는 방식이지만 너무나 당연하게 5의 개수가 더 적다.)

79 이하의 숫자 중 5의 배수는 79를 5로 나눠서 버림한 값인 15가 된다. (5, 10, 15, 20, ... 75)

12 이하의 숫자 중 5의 배수는 12를 5로 나눠서 버림한 값인 2가 된다. (5, 10)

이러한 성질을 이용하여 5, 25, 125로 나누는 것이다. 그렇다면 왜 5로만 나누는 것이 아니라 25, 125로도 나누는 것일까?

25의 경우에는 5의 제곱으로 10이 두개 만들어지게 된다. 그렇다면 0이 2개가 되는 것이다. 5로 나눴을 때 한번 카운트, 25로 나눴을 때 한번 카운트가 되어서 총 2번 카운트가 되어야 한다. 125의 경우도 마찬가지이다.

125까지만 하는 이유는, n이 500 미만이기 때문이다.

 

 

 

2004. (조합 0의 개수) 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

#include<iostream>
using namespace std; 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	int countf = 0;
	int countt = 0;
	for (long long i = 5; i <= n; i *= 5)
	{
		countf += n / i;
	}
	for (long long i = 2; i <= n; i *= 2)
	{
		countt += n / i;
	}
	for (long long i = 5; i <= m; i *= 5)
	{
		countf -= m / i;
	}
	for (long long i = 2; i <= m; i *= 2)
	{
		countt -= m / i;
	}
	for (long long i = 5; i <= n - m; i *= 5)
	{
		countf -= (n - m) / i;
	}
	for (long long i = 2; i <= n - m; i *= 2)
	{
		countt -= (n - m) / i;
	}
	if (min(countf, countt) < 0)
		cout << 0;
	else
		cout << min(countf, countt);
}

n과 m이 2,000,000,000 이므로 int로 해주어도 된다. 하지만 2나 5를 곱하면 그것보다 커지므로 for 문에서는 long long으로 선언을 해주어야 한다. 

int	-21억 ~ 21억	-2^31~2^31
long long	-9*10^18 ~9*10^18	-2^63~2^63

 

 

 

9613. (GCD 합) 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

#include<iostream>
#include<vector>
using namespace std; 
int gcd(int x, int y) {
	if (x % y == 0)
		return y;
	else
		return gcd(y, x % y);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int t, n;
	cin >> t;
	while (t--) {
		long long result = 0;
		cin >> n;
		vector<int> v(n);
		for (int i = 0; i < n; i++)
		{
			cin >> v[i];
		}
		for (int i = 0; i < v.size() - 1; i++)
		{
			for (int j = i + 1; j < v.size(); j++)
			{
				result += gcd(v[i], v[j]);
			}
		}
		cout << result << "\n";
	}
}

gcd는 최대공약수를 뜻한다. 자료형에서 int만으로도 충분할거라고 예상했는데 아니었다. 

최대 100개인 수를 2개씩 짝지어서 계산하면 100*99/2로 n(n-1)/2가 된다. 여기서 최대공약수가 나오는데 이 수의 범위가 최대 1,000,000이니까 총 합의 최대값이 100*99/2*1,000,000으로 약 49억이 나온다. int는 최대 21억이므로 long long을 사용해야 한다. long long은 +-900경이다.

 

 

 

17087. (숨바꼭질 6) 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int gcd(int x, int y) {
	if (x % y == 0)
		return y;
	else
		return gcd(y, x % y);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, s;
	cin >> n >> s;
	vector <int> d;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		d.push_back(abs(x - s));
	}

	int result = d[0];
	for (int i = 0; i < n - 1; i++)
	{
		result = gcd(result, d[i + 1]);
	}
	cout << result;
}

처음에 문제 이해를 잘 못해서 예제를 보고 이해했다. 어떤 간격으로 이동해야 동생을 만날 수 있는지 물어보는 문제이다. 즉, 최대공약수를 구해야 한다.

두 수의 최대공약수와 나머지 한 수의 최대공약수가 세 수의 최대공약수가 된다. 네 수 이상에서도 같은 방법으로 계산할 수 있다.

 

 

1373. (2진수 8진수) 2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오.

#include<iostream>
using namespace std;

int translate(int x, int y, int z) {
	return x * 4 + y * 2 + z;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string num;
	cin >> num;
	if (num.length() % 3 == 1) {
		cout << translate(0, 0, num[0] - '0');
	}
	else if (num.length() % 3 == 2) {
		cout << translate(0, num[0] - '0', num[1] - '0');
	}

	for (int i = num.length() % 3; i < num.length() - 1; i += 3)
	{
		cout << translate(num[i] - '0', num[i + 1] - '0', num[i + 2] - '0');
	}
}

2진수를 8진수로 바꾸는 방법을 알면 풀 수 있다.

 

 

 

1212. (8진수 2진수) 8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오.

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

string translate(int x) {
	string result = "000";
	for (int i = 2; i >=0; i--)
	{
		result[2 - i] = x / int(pow(2, i)) + '0';
		x %= int(pow(2, i));
	}
	return result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string num;
	cin >> num;
	if (num[0] - '0' < 2) {
		cout << translate(num[0] - '0')[2];
	}
	else if (num[0] - '0' < 4) {
		string temp = translate(num[0] - '0');
		for (int i = 1; i < 3; i++)
		{
			cout << temp[i];
		}
	}
	else {
		cout << translate(num[0] - '0');
	}
	for (int i = 1; i < num.length(); i ++)
	{
		cout << translate(num[i] - '0');
	}
}

to_string 함수 : string 값으로 변환, 변환 후 연산기호로 string 문장에 추가할 수가 있다.

https://minyeok2ee.gitlab.io/boj/boj-1212/

[BOJ][C++] 백준 1212번 8진수 2진수

to_string을 이용해서 구현하셨길래 첨부한다.

 

 

 

2089. (-2진수) 10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오.

-2진수가 뭔가 했는데 진짜 2진수 찾듯이 똑같이 하면 되는 거였다.

태블릿으로 대충 끄적여봤는데, 이런식으로 풀면 된다. 중요한 건 -1/-2의 경우 0이 아닌 1로 몫이 나와야 한다는 것이었다. 

cout << -1 / -2; // 0
cout << -1 % -2; // -1

c++의 경우 주석과 같은 결과값이 나오게 된다.

#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	stack <int> s;
	int n;
	cin >> n;
	if (n == 0) {
		cout << 0;
		return 0;
	}
	while (n != 0 && n != 1) {
		if (n > 0) {
			s.push(n % -2);
			n /= -2;
		}
		else {
			// -1 = -2*1 + 1
			int temp = n;
			n = ceil(n / -2.0);
			s.push(temp + n * 2);
		}
	}
	if (n == 1) {
		s.push(n);
	}

	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
}

올림 함수인 ceil을 사용하였다.

#include<cmath>를 하면 올림함수 ceil, 내림함수 floor, 반올림함수 round를 사용할 수 있다. 모두 double 형을 반환한다.

소수점 n번째 자리에서 반올림을 할려면 (3.47 -> 3.5)

round(3.47 * 10) / 10;

이와 같이 자리수를 조정해주어야 한다.

또한 몇번째 자리까지 나타내기 위해서는 precision과 fixed를 이용해야 한다.

precision은 n개의 숫자만 나타내는 함수 (자동 반올림), fixed는 소수점을 고정시키는 함수이다.

double num = 3.141592;
cout.precision(4);
cout << num << endl; // 3.142 (자동 반올림 + 앞에서부터 4개)

cout << fixed;
cout.precision(4);
cout << num << endl; // 3.1416 (자동 반올림 + 소수점부터 4개)

fixed와 precision을 사용하는 방법이다.

 

 

 

17103. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<bool>prime(1000001, 1);
void findPrime() {
	prime[0] = 0;
	prime[1] = 0;
	for (long long i = 2; i < 1000001; i++)
	{
		if (prime[i] == 0)
			continue;
		for (long long j = i * i; j < 1000001; j += i)
		{
 			prime[j] = 0;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	findPrime();
	int t, n, count = 0;
	cin >> t;
	
	while (t--) {
		cin >> n;
		int count = 0;
		for (int i = n - 2; i >= n / 2; i--)
		{
			if (prime[i] == 1 && prime[n - i] == 1)
				count++;
				//cout << i << " + " << n - i << " = " << n << endl;
		}
		cout << count << "\n";
	}

}

에라토스테네스의 체 방법을 사용해야 한다. 예전엔 j의 시작값을 2*i로 했는데, 이미 2에서 i*2는 검사를 했을테니 i*i부터 확인하면 된다.

https://nanyoungkim.tistory.com/32

[C++] 백준 1929 - 소수 구하기 (에라토스테네스의 체)

이해가 안됐다면 위 블로그 3번을 읽어보는 것을 추천한다.

그리고 나는 숫자 n부터 2까지 다 도는 것보다 반까지만 도는 것이 맞다고 생각했다. 예를 들어 6의 경우 5, 4, 3까지만 확인해도 충분하다. 왜냐면 6=2+4=4+2이기 때문이다.