굉장히 유용한 챕터였다.
예전부터 관련된 문제를 해결하는 것은 어렵지 않았는데, 세련되지 않게 푸는 느낌이 들 때가 많았다.
다른 방법이 있을 것만 같은 느낌이 강하게 들었는데, 이번 챕터로 그 찝찝함을 해결한 느낌이 들어서 기분이 좋다.
아리까리 할 때 자주 찾을 것만 같은, 수학1 정리 시작!
-
* 나머지 연산: 답이 엄청 커질 때, 어떤 수로 나눈 나머지를 답으로 요구하는 경우가 있다. 결과값의 나머지를 바로 구할 수도 있지만 그게 너무 커져버리면 오버플로우가 나서 계산을 못 하는 경우도 생긴다. 그런 일이 안 생기게 계산 과정에서 나머지 연산을 해주는 방법이 있다.
- (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) + M ) mod M (음수가 될 수도 있기 때문에)
- 나누기는 성립 x
=> 뺄셈 연산에 주의!
* 최대공약수: GCD. A와 B의 공통된 약수 중에서 가장 큰 정수. 2부터 min(A,B)까지 나눠보는 게 가장 직관적인 방법.
- 유클리드 호제법: 좀 더 빠르게 최대공약수를 구할 수 있다. a % b = r일 때, GCD(a,b) = GCD(b, r) 임을 이용해서 반복 계산하고, r이 0일 때의 b 값이 최대공약수가 된다. 재귀를 써서 구현할 수도, 안 써서 구현할 수도 있다.
* 최소공배수: LCM. A와 B의 공통된 배수 중에서 가장 작은 정수. A*B / GCD(A,B)로 구할 수 있다.
유클리드 호제법을 사용해 최대공약수와 최소공배수 구하는 문제를 풀어봤다.
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
|
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>
using namespace std;
/* 재귀 사용
int gcd(int x, int y)
{
if (y == 0)
return x;
else
return gcd(y, x%y);
}
*/
int gcd(int x, int y)
{
while (y != 0) {
int r = x%y;
x = y;
y = r;
}
return x;
}
int main()
{
int a, b;
cin >> a >> b;
cout << gcd(a, b) << '\n';
cout << (a*b) / gcd(a, b) << '\n';
return 0;
}
|
cs |
- 재귀가 직관적이긴 한데, 수가 커지면 골치 아플 수도 있으니 왠만하면 재귀 없는 버전으로 쓰자.
* 소수: 약수가 1과 자신 밖에 없는 수. N이 소수가 되려면 2~N-1인 자연수로 나누어 떨어지면 안 된다.
관련된 알고리즘은 크게 두 개로 나뉜다.
1. N이 소수인지 아닌지 판별
우선 가장 직관적인 방법으로 구하는 방법이다.
|
1
2
3
4
5
6
7
8
9
10
|
bool prime(int n) {
if (n < 2) {
return false;
}
for (int i=2; i<=n-1; i++) {
if (n%i == 0)
return false;
}
return true;
}
|
cs |
- 정의 그대로 2에서 N-1까지의 수로 나누어 떨어지는지 확인한다. 근데 굳이 N-1까지 확인 해야할까?
- N을 a*b 꼴로 나타낸다면 a, b에 들어갈 수 있는 가장 작은 소수는 2가 될 것이고, 나머지 수는 N/2가 된다.
- 따라서 굳이 N-1까지 확인하지 않고 N/2까지만 확인해도 N이 소수인지 판별할 수 있다. (n-1를 n/2로만 바꾸면 된다)
- 근데 시간 복잡도는 O(n)으로 똑같다. 더 빠른 방법은 없을까?
- N을 a*b 꼴로 나타낼 수 있다면, a >= √N 일 때, b <= √N 임을 알 수 있다.
- 따라서 √N까지만 확인을 해도 N이 소수인지 판별이 가능하다. 실수값을 넣는 것을 피하기 위해,
|
1
2
3
4
5
6
7
8
9
10
|
bool prime(int n) {
if (n < 2) {
return false;
}
for (int i=2; i*i<=n; i++) {
if (n%i == 0)
return false;
}
return true;
}
|
cs |
이런 꼴로 나타낼 수 있다. 시간 복잡도는 무려 O(√N). 당연히 이거 써야겠지?
문제 한번 풀어보자.
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
|
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
|
#include <iostream>
using namespace std;
bool prime(int k)
{
if (k < 2)
return false;
else {
for (int i = 2; i*i <= k; i++) {
if (k % i == 0)
return false;
}
return true;
}
}
int main()
{
int n, cnt = 0;
int a[100];
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++) {
if (prime(a[i]))
cnt += 1;
}
cout << cnt;
return 0;
}
|
cs |
- 구하려는 숫자가 커질 수록, O(√N)은 위력을 발휘한다!
2. N보다 작거나 같은 모든 자연수 중에서 소수 찾기
그럼 N 이하의 소수를 구하는 방법은 O(N√N)일까? 더 빠른 방법이 있다.
- 에라토스테네스의 체: 2부터 N까지 모든 수를 써놓고, 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는데, 그 수는 소수이다. 선택된 수는 남겨 놓고, 그 수의 배수를 모두 지운다. 이를 반복한다. 아래는 100이하의 소수를 구하는 코드.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
int prime[100]; // 소수 저장
int pn = 0; // 소수 개수
bool check[101] = {false,}; // true면 소수가 아니다
int n = 100;
for (int i=2; i<=n; i++) {
if (check[i] == false) {
prime[pn++] = i;
for (int j=i*2; j<=n; j+=i) {
check[j] = true;
}
}
}
|
cs |
- 8: 직관적으로 생각하면 i*(i-1)까지는 처리가 됐을 것이므로 i*i부터 반복문을 시작해야 한다. 근데 i가 커지면 오버플로우가 발생할 위험이 있다. 안전하게 i*2부터 시작하는 것이 좋다.
문제 한번 풀어보자.
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
|
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
|
#include <iostream>
#include <vector>
#define MAX 1000000
using namespace std;
int main()
{
vector<int>prime;
bool check[MAX+1] = { false, };
check[0] = check[1] = true;
for (int i = 2; i*i <= MAX; i++) {
if (check[i] == false) {
prime.push_back(i);
for (int j = i * 2; j <= MAX; j += i) {
check[j] = true;
}
}
}
int m, n;
cin >> m >> n;
for (int i=m; i<=n; i++) {
if(check[i] == false)
cout << i << '\n';
}
return 0;
}
|
cs |
=> 이런 문제에서는 해당 되는 범위의 소수만 구하기 보다는, 그냥 가능한 범위 안에 해당하는 소수를 다 구해서 m에서 n 사이 수만 출력하는 게 더 낫다.
- 골드바흐의 추측: 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다는 추측이다. 10^18이하에서는 참인 것이 증명되어 있다. 에라토스테네스의 체를 이용해서 한번 풀어보자.
6588번: 골드바흐의 추측
문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
www.acmicpc.net
|
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
|
#include <iostream>
#include <vector>
#define MAX 1000000
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
vector<int>prime;
bool check[MAX + 1] = { false, };
for (int i = 2; i*i <= MAX; i++) {
if (check[i] == false) {
prime.push_back(i);
for (int j = i * 2; j <= MAX; j += i) {
check[j] = true;
}
}
}
int n;
cin >> n;
while (n != 0) {
int idx = 1;
while (idx < prime.size()) {
if (check[n - prime[idx]] == false) {
cout << n << " = " << prime[idx] << " + " << n - prime[idx] << '\n';
break;
}
idx += 1;
}
if (idx == prime.size())
cout << "Goldbach's conjecture is wrong.";
cin >> n;
}
return 0;
}
|
cs |
=> 위에서 푼 것처럼 에라토스테네스의 체를 이용해 범위 내 소수를 모두 구해놓고 구한다.
-29: n에서 소수를 뺀 값도 소수면 골드바흐의 추측이 적중한 것이다.
*팩토리얼: n! = 1 * 2 * ... * n / 매우 큰 값이다. 원리를 이해하는 것은 그닥 어렵지 않으므로 바로 문제를 풀어본다.
1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
|
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 <vector>
using namespace std;
int main()
{
int n, ans = 0;
cin >> n;
int tmp = 5;
while (n >= tmp) {
ans += n / tmp;
tmp *= 5;
}
cout << ans;
return 0;
}
|
cs |
=> 0의 개수는 10을 만드는 개수이고, 10을 만들려면 2와 5가 필요하다. 순차적으로 곱하는 팩토리얼의 특성상 어떤 수든 5보다 2가 많이 나온다. 따라서 5의 개수를 구하면 그게 10의 개수, 즉 0의 개수라고 할 수 있다.
- 조합 0의 개수: 분수 형태로 곱해지는 조합의 특성상, 2와 5중 어느 수가 더 많다고 판단할 수 없다. 따라서 2와 5의 개수를 둘 다 구하고, 그 중 적은 것을 0의 개수라고 생각하면 된다.
2004번: 조합 0의 개수
첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.
www.acmicpc.net
|
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
45
46
47
48
49
50
51
52
|
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct _cz
{
long long c2, c5;
} cz;
long long cnt2(long long a) {
long long t = 2, ans = 0;
while (a >= t) {
ans += a / t;
t *= 2;
}
return ans;
}
long long cnt5(long long a) {
long long t = 5, ans = 0;
while (a >= t) {
ans += a / t;
t *= 5;
}
return ans;
}
int main()
{
long long n, m;
cin >> n >> m;
cz son, parent;
long long a2, a5;
son.c2 = cnt2(n);
son.c5 = cnt5(n);
parent.c2 = cnt2(n - m) + cnt2(m);
parent.c5 = cnt5(n - m) + cnt5(m);
a2 = son.c2 - parent.c2;
a5 = son.c5 - parent.c5;
cout << min(a2, a5) << '\n';
return 0;
}
|
cs |
=> 입력 가능한 정수의 범위가 무려 20억이나 되니 long long 형으로 계산 해야한다..
-
여러모로 많은 꿀팁을 얻을 수 있었던 챕터였다. 잘 기억해뒀다가 나중에 많이 써먹자.
열심히 보다 꾸준히 하자. 화이팅!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 1 + 기초 예제 (0) | 2020.07.08 |
|---|---|
| 백준 알고리즘 기초 - 수학1 (연습) (0) | 2020.07.07 |
| 백준 알고리즘 기초 - 자료구조1 (연습) (0) | 2020.07.06 |
| 백준 알고리즘 기초 - 자료구조1 (큐, 덱) (0) | 2020.07.06 |
| 백준 알고리즘 기초 - 자료구조1 (스택) (0) | 2020.07.04 |
