천천히 빛나는
백준 알고리즘 기초 : 수학 본문
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
유클리드 호제법은 위 티스토리에 자세히 나와있다.
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://minyeok2ee.gitlab.io/boj/boj-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/
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
이해가 안됐다면 위 블로그 3번을 읽어보는 것을 추천한다.
그리고 나는 숫자 n부터 2까지 다 도는 것보다 반까지만 도는 것이 맞다고 생각했다. 예를 들어 6의 경우 5, 4, 3까지만 확인해도 충분하다. 왜냐면 6=2+4=4+2이기 때문이다.
'C++ > BAEKJOON (C++)' 카테고리의 다른 글
백준 : DFS, BFS 기본문제 (1) | 2023.10.08 |
---|---|
백준 알고리즘 기초 : 자료구조 (2) (0) | 2023.09.28 |
백준 알고리즘 기초 : 자료구조 (1) (1) | 2023.09.28 |
백준 단계 13 : 정렬 (C++) (0) | 2023.09.17 |
백준 단계 12 : 브루트 포스 (C++) (0) | 2023.09.11 |