이번엔 3강이다! 얼른 듣자!!
이번 강의에서는 알고리즘을 공부할 때 필요한 기초적인 수학 관련 내용이었다. 그 중에서도 나머지연산, 최대공약수, 소수와 팩토리얼에 대해 배웠다.
-나머지 연산
나머지 연산은 말 그대로 수의 나머지를 구하는 연산이다. 나머지 연산을 할 때 연산을 다해서 나머지를 구하면 오래걸리기도 하고 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에 직접 연산하지 않고 나머지만 구한다. (직접 연산하는 경우 int나 long long과 같은 자료형의 범위를 넘어갈 수 있다)
> (A+B) % M = ((A%M) + (B%M)) % M
> (A*B) % M = ((A%M) * (B%M)) % M
이는 나누기의 경우에는 성립하지 않는다.
또한 빼기의 경우에는 음수가 나올 수 있기 때문에 아래와 같이 해야한다.
> (A-B) % M = ((A%M) - (B%M) + M) % M
- 최대공약수
최대공약수는 줄여서 GCD라고 하며 이를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법이 있다. 이 때 최대공약수가 1인 두 수는 서로소(Coprime)이라고 한다. 이 때 max(A, B)가 N인 경우 시간 복잡도는 O(N)이다.
하지만 위의 방법보다 빠른 방법이 있다. 바로 유클리드 호제법(Euclideam algorithm)이다. 이는 a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a,b) = GCD(b,r)과 같고, r이 0이면 그 때 b가 최대 공약수가 된다.
ex) GCD(24,16) = GCD(16,8) = GCD(8,0) = 8
이는 재귀함수를 사용하여 구현할 수 있고 재귀함수를 사용하지 않고 반복문을 통해서도 구현할 수 있다. 이 때의 시간복잡도는 O(logN)이다.
세 수의 최대공약수는 GCD(a,b,c) = GCD(GCD(a,b),c) 이런식으로 구할 수 있다.
최소공배수는 줄여서 LCM이라고 하며 이는 GCD를 응용ㅎ여 구할 수 있다. a,b의 최대공약수를 g라고 하면 최소공배수는 다음과 같이 구할 수 있다.
> l = g * (a/g) * (b/g)
<2609번 / 최대공약수와 최소공배수>
유클리드 호제법을 통해 gcd를 먼저 구하고 그를 통해 lcm을 구하였다.
|
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 <string> using namespace std; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int a, b; cin >> a >> b; int max, min; max = gcd(a, b); min = max * (a / max)*(b / max); cout << max << '\n' << min << '\n'; return 0; } |
cs |
<1934번 / 최소공배수>
위의 문제를 거의 바꾸지 않고 그냥 lcm구하는 함수를 하나 더 만들어서 쉽게 구현하였다!
|
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 |
#include <iostream> #include <string> using namespace std; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); } int lcm(int a, int b) { int max = gcd(a, b); return max * (a / max)*(b / max); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; while (n--) { int a, b; cin >> a >> b; cout << lcm(a, b) << '\n'; } return 0; } |
cs |
-소수
소수는 약수가 1과 자기 자신밖에 없는 수로 N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 이와 관련된 알고리즘은 두 가지가 있다.
1. 어떤 수 N이 소수인지 아닌지 판별하는 방법
2. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법(N이하의 모든 소수를 찾는 방법)
첫번째 알고리즘은 반복문을 통해 구현하며 이의 시간복잡도는 O(N)이 된다.
N개의 수를 모두 하는 것보다 그나마 조금 더 효율적인 방법이 있다. N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문에 N이 소수가 되려면 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 즉, N/2까지만 검사해보면 된다는 것이다. 만약 N=a*b이고, a<=b이면 a는 2, b는 N/2로 표현이 가능하기 때문에 (N/2+1)~(N-1)까지는 약수가 존재하지 않는다! 이 때의 시간복잡도는 O(N/2)=O(N)으로 결국 처음 방법과 같다.
다음 방법은 루트 N까지만 검사하는 것이다. 왜냐하면 N이 소수가 아니라면 N =a*b(a<=b)로 나타낼 수 있으며 a<=루트 N, b>=루트 N이기 때문에 a와 b의 차이가 가장 작은 경우는 루트 N이다. 따라서 루트 N까지만 검사해보면 된다. 이를 코드로 표기할 땐 루트 N대신 i^2이 N인 경우처럼 제곱으로 표현해주는 것이 좋다. 이 때의 시간복잡도는 O(루트N)이다.
<1978번 / 소수 찾기>
소수 찾는 함수를 만들어서 i^2이 N보다 작은 경우, 즉 루트N까지 검사하여 소수 판별을 하도록 하였다.
|
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 |
#include <iostream> using namespace std; bool prime(int a) { if (a < 2) return false; for (int i = 2; i*i <= a; i++) { if (a%i == 0) return false; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int num = 0; while (n--) { int a; cin >> a; if (prime(a) == true) num++; } cout << num << '\n'; return 0; } |
cs |
어떤 수 N이 소수인지 판별하는데 걸리는 시간 복잡도는 O(루트 N)이었다. 그러면 N까지의 소수 개수를 구하는데 걸리는 시간복잡도는 총 N개의 수를 검사해야 하기 때문에 O(N루트N)이 된다. 이러면 너무 긴 시간이 걸리게 된다.
그래서 위보다 빠른 방법을 사용한다. 바로 "에라토스테네스의 체" 알고리즘이다.
-에라토스테네스의 체
1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.
1) 2부터 N까지 모든 수를 써놓는다.
2) 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3) 그 수는 소수이다.
4) 이제 그 수의 배수를 모두 지운다.
위 과정을 마치고 남은 수는 모두 소수이다. 만약 2부터 100까지의 소수를 찾는 경우에는 11부터는 검사를 하지 않아도 된다. 왜냐하면 11의 배수는 이미 모두 지워져있고 다음으로 지울 배수는 11의 제곱인데, 이는 100을 넘기 때문에 확인하지 않아도 된다. 알고리즘에서 바깥 for문은 N까지 돌리고, 안쪽 for문은 N의 크기에 따라서 i^2 또는 i*2로 바꾸는게 좋다. 이 때의 시간 복잡도는 O(NloglogN)이다.
<1929번 / 소수 구하기>
에라토스테네스 구하는 반복문에서 안쪽 for문의 j를 i*i로 했더니 런타임 에러가 났다. 그래서 이를 i*2로 바꿨더니 해결되었다. 배열의 크기를 크게 잡고 여기서 입력받은 수만큼의 소수를 구해주고 출력하면 된다.
|
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 |
#include <iostream> using namespace std; int num[1000001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int m, n; cin >> m >> n; for (int i = 2; i <= n; i++) { num[i] = i; } for (int i = 2; i <= n; i++) { if (num[i] != 0) { for (int j = 2 * i; j <= n; j += i) { num[j] = 0; } } } for (int i = m; i <= n; i++) { if (num[i] != 0) cout << num[i] << '\n'; } return 0; } |
cs |
-골드바흐의 추측
골드바흐의 추측이란 "2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다"는 것이다. 또한 여기다 3을 더하면 "5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다"로 바뀐다. (이건 약한 추측임) 이는 아직 증명되지 않았지만 10^18이하에서는 참인 것이 증명되었다.
<6588번 / 골드바흐의 추측>
에라토스테네스의 체를 통해 소수를 미리 구해놓고 입력받은 수에서 그 보다 작은 소수를 찾고 입력받은 수 - 소수를 순서대로 출력하여 골드바흐의 추측을 증명한다.
|
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 |
#include <iostream> using namespace std; #define MAX 1000000 int prime[MAX]; int pn; int check[MAX + 1]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); for (int i = 2; i <= MAX; i++) { if (check[i] == false) { prime[pn++] = i; } for (int j = i * 2; j <= MAX; j += i) { check[j] = true; } } while (1) { int n; cin >> n; if (n == 0) break; for (int i = 1; i < pn; i++) { if (check[n - prime[i]] == false) { cout << n << " = " << prime[i] << " + " << n - prime[i] << '\n'; break; } } } return 0; } |
cs |
에라토스테네스의 체를 사용한 경우 루트 N 방법을 사용할 필요가 없다고 한다. 소수는 6n+1, 6n+5만 해당된다. 6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5에서 +1과 +5를 제외하고는 모두 약수가 존재한다. 따라서 6의 배수로 에라토스테네스의 체를 실시할 수 있는데 이는 이론상으로는 6배 빨라질 것같지만 실제로는 속도상에서 크게 차이나지 않는다. (애초에 에라토스테네스의 체가 빠르기 때문)
-팩토리얼
팩토리얼은 매우 큰 값이다. 따라서 20!만 해도 int 정수 표현의 범위를 벗어나게 된다.
<10872번 / 팩토리얼>
단순 반복문으로 해결 가능!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int res = 1; for (int i = 2; i <= n; i++) { res *= i; } cout << res << '\n'; return 0; } |
cs |
<1676번 / 팩토리얼 0의 개수>
팩토리얼을 실제로 구하려면 그를 표현하기엔 언어의 정수 범위가 부족하다. 그래서 0의 개수를 물어보는 문제가 자주 등장한다. 이는 소인수 분해해서 5의 개수와 같다. 그래서 숫자를 5의 배수로 나눈 몫의 합이 0의 개수가 된다.
N!의 0의 개수 = [N/5] + [N/5^2] + [N/5^3] + ...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int num = 0; for (int i = 5; i <= n; i *= 5) { num += (n / i); } cout << num << '\n'; return 0; } |
cs |
<2004번 / 조합 0의 개수>
조합 nCm은 n!/(n-m)!m! 과 같다. 그리고 팩토리얼에서는 2의 배수가 5의 배수보다 무조건 컸던 반면, 조합에서는 이를 알 수 없기 때문에 2와 5의 배수의 개수를 모두 구하고 이중에서 작은 값이 0의 개수가 된다. 따라서 n!, (n-m)!, m!의 2와 5의 배수의 개수를 세야 한다.
여기서 처음에 int로 했을때 런타임에러가 나왔다. 그래서 long long으로 변수형만 바꿨더니 맞았다. 찾아보니 long long이 int형보다 데이터 처리 크기?가 커서 속도가 빠른것 같았다. 그리고 int로 하면 범위가 작아서 큰 값을 입력하면 범위를 초과하게 되어 int보단 long long을 사용하는게 더 좋은 것 같다.
|
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 |
#include <iostream> #include <algorithm> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long two = 0, five = 0; long long n, m; cin >> n >> m; for (long long i = 2; i <= n; i *= 2) { two += n / i; } for (long long i = 2; i <= n-m; i *= 2) { two -= (n - m) / i; } for (long long i = 2; i <= m; i *= 2) { two -= m / i; } for (long long i = 5; i <= n; i *= 5) { five += n / i; } for (long long i = 5; i <= n - m; i *= 5) { five -= (n - m) / i; } for (long long i = 5; i <= m; i *= 5) { five -= m / i; } cout << min(two, five) << '\n'; return 0; } |
cs |
끝~ 다음은 수학 연습이지렁
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 3강 수학 1 - 연습 (0) | 2020.08.20 |
|---|---|
| 2강 자료구조 1 - 참고 (0) | 2020.08.20 |
| 2강 자료구조 1 - 연습 (0) | 2020.08.16 |
| 2강 자료구조 1 - 큐와 덱 (0) | 2020.08.10 |
| 2강 자료구조 1 - 스택 (0) | 2020.08.09 |
댓글