개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.
정수론
1. 모듈러의 성질
모듈러 연산이란?
쉽게 나머지 연산을 의미한다.
cout << 5 % 3; // 1
cout << (5 + 8) % 3; // 1
cout << (5 % 3 + 8 % 3) % 3; // 1
두번째 코드와 3번째 코드를 보면 알 듯이 분배법칙이 성립함을 알 수 있다.
분배법칙이 성립하므로 다음의 식들도 성립한다.
(a + b) % c == (a%c + b%c) % c
(a * b) % c == (a%c * b%c) % c
(a - b) % c == (a%c - b%c + c) % c
== (a%c - b%c + kc)%c (k는 임의의 양수 가능)
( +c나 +kc 가 들어가는 이유는. 만약 a - b의 값이 음수가 된다면, 원하는 값이 나오지 않기 때문에
어짜피 사라지는 c의 배수를 더해줌으로써 음수가 나오는 것을 방지.)
C++의 경우
int 자료형의 경우 21억까지 표기가 가능 그 이후에는
long long 을 사용해야 한다. long long의 경우에는 21억 * 21억 * 2까지 가능하다고 함.
당연한 말이지만 숫자가 커질수록 연산 속도는 당연히 느려지게 되고, 이를 해결하기 위해서
간혹가다 소수로 나눠주는 경우가 생기게 된다. (알고리즘 문제의 경우 문제에서 주어짐)
예를들면 다음과 같은 문제가 나왔다고 하면
1부터 10000000000의 합의 % 1000000007 구하기
위의 분배 법칙을 이용해 빠른 속도로 문제를 해결할 수 있다. (overflow도 막을 수 있음.)
int total = 0;
for(int i = 1; i < 10000000001; i++){
total += i;
total %= 1000000007
};
cout << total;
2. 소수 판정
자연수를 받아, 이 수가 소수면 YES, 소수가 아니면 No를 출력하는 코드를 짜보도록 하자
(소수 판정에서는 항상 1을 조심해야 한다. // 소수 : 1과 자기 자신만을 약수로 갖는 자연수)
1. 완전탐색을 이용한 소수판정
// 1. 완전 탐색을 이용하여 소수판정
// n이 10^12 이상으로 나오면 시간초과가 나온다.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int cnt = 0;
for(int i = 1; i < n + 1; i++) {
if(n % i == 0) {
cnt++;
}
}
if(cnt == 2) {
cout << "YES";
} else {
cout << "NO";
}
return 0;
}
2. 1 ~ root n까지의 약수를 이용한 방법
// 2. 1~ root n까지의 약수가 정확히 하나인지 구한다.
// 이론
// 12의 약수
// 1 2 3 4 6 12
// (1, 12) (2, 6) (3, 4)으로 순서쌍을 이루므로 root까지의 약수가 1개임을 구하면 소수임을 알 수 있다.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int cnt = 0;
for(int i = 1; i < n + 1; i++) {
if(i * i > n) break;
if(n % i == 0) {
cnt++;
}
}
if(cnt == 1) {
cout << "YES";
} else {
cout << "NO";
}
return 0;
}
3. 약수구하기
1. 완전 탐색을 이용한 방법
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> prime;
for(int i = 1; i < n + 1; i++) {
if(n % i == 0) {
prime.push_back(i);
}
}
for(int i = 0; i < prime.size(); i++) {
cout << prime[i] << " ";
}
return 0;
}1 ~ n까지의 수를 모두 돌면서 해당 수가 약수인지 판별한다.
2. 순서쌍을 이용한 방법
해당 방법은 제곱수를 조심해야 한다.
// 약수의 개수가 홀수 < = > 제곱수랑 필요충분조건이다 (동치이다)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> prime;
for(int i = 1; i < n + 1; i++){
if(i * i > n) break;
if(n % i == 0) {
prime.push_back(i);
if (i * i != n) {
prime.push_back(n / i);
}
}
}
for(int i = 0; i < prime.size(); i++){
cout << prime[i] << " ";
}
// 정렬을 추가한다면
cout << endl;
sort(prime.begin(), prime.end());
for(int i = 0; i < prime.size(); i++){
cout << prime[i] << " ";
}
return 0;
}4. 소인수 분해
1. 완전탐색을 이용한 방법
// 완전 탐색을 이용한 방법.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for(int i = 2; i < n + 1; i++) {
while(n % i == 0){
cout << i << " ";
n /= i;
}
}
return 0;
}
2. 1 ~ root n을 이용한 방법
// n =a, b, c, d, e, f, g, h, i
// a * b * c * d * e * f * g * h * i = n
// 소인수가 sqrt n 보다 큰 경우는 1개이거나 없다. ==> 제곱수
#include <iostream>
using namespace std;
int main() {
int n, x;
cin >> n;
x = n;
for(int i = 2; i < n + 1; i++) {
if(i * i > n) break;
while(x % i == 0) {
cout << i << " ";
x /= i;
}
}
if (x != 1) {
cout << x << " ";
}
return 0;
}
범위를 제한하는 방법이다. (쓸모없는 연산을 피함)
5. 유클리드 호제법
- 목표: 두 자연수 a, b가 주어질 때 이 둘의 최대 공약수를 구한다. ( log n)
- a < b일 때, a와 b - a를 남기는 작업을 반복하면 된다.
1. 최대 공약수를 구하는 방법
// 최대 공약수를 구하는 방법 (GCD)
#include <iostream>
using namespace std;
int main() {
int a, b; // a > b라고 가정.
cin >> a >> b;
int temp;
while(a % b != 0) {
temp = a;
a = b;
b = temp % b;
}
cout << b;
return 0;
}
2. 최소 공배수를 구하는 방법
// 최소공배수를 구하는 방법(LCM)
// 유클리드 호제법의 응용
#include <iostream>
using namespace std;
int main() {
int a, b; // a > b라고 가정.
cin >> a >> b;
int A, B;
A = a;
B = b;
int temp;
while(a % b != 0){
temp = a;
a = b;
b = temp % b;
}
cout << A * B / b;
return 0;
}
6. 에라토스테네스의 체
1. 완전 탐색을 이용한 방법
// 목표 : 1 ~ n까지의 자연수 중 소수를 모두 출력한다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> isPrime(n + 1, 1);
isPrime[0] = false;
isPrime[1] = false; // 1은 소수가 아니므로,
for(int i = 2; i < n + 1; i++) {
if(not isPrime[i]) continue;
for(int j = 2 * i; j < n + 1; j += i) {
isPrime[j] = false;
}
}
for(int i = 0; i < n + 1; i++) {
if (isPrime[i]) cout << i << " ";
}
return 0;
}
2. 1 ~ root n까지를 탐색하는 방법
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> isPrime(n + 1, 1);
isPrime[0] = false;
isPrime[1] = false; // 1은 소수가 아니므로,
for(int i = 2; i < n + 1; i++) {
if(not isPrime[i]) continue;
for(int j = i * i; j < n + 1; j += i) {
isPrime[j] = false;
}
}
for(int i = 0; i < n + 1; i++) {
if (isPrime[i]) cout << i << " ";
}
return 0;
}+ 응용
// 2 ~ n 까지의 자연수 각각의 가장 작은 소인수 출력
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> prime(n + 1, -1);
for(int i = 2; i < n + 1; i++) {
if(prime[i] != -1) continue;
prime[i] = i;
for(int j = i * i; j < n + 1; j += i){
if(prime[j] == -1) {
prime[j] = i;
}
}
}
for(int i = 2; i < prime.size(); i++) {
cout << prime[i] << " ";
}
return 0;
}7. 빠른 거듭제곱
1. 계산 테크닉을 이용한 방법
(n**m) % 1000000007 (n<=100, m<=1,000,000,000,000,00,000)
# 파이썬의 경우에는
pow(n, m, 1000000007)
3**28을 구한다고 하자. 아래와 같은 방법으로 시간을 줄이는 테크닉이 가능하다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int ans;
for(int i = 0; i < 28; i++) {
ans *= 3;
ans %= 1000000007;
}
// 밑의 코드는 같은 방법을 말함.
int ans;
for(int i = 0; i < 14; i++) {
ans *= 3;
ans %= 1000000007;
}
ans *= ans;
ans %= 1000000007;
//
int ans;
for(int i = 0; i < 7; i++) {
ans *= 3;
ans %= 1000000007;
}
ans *= ans;
ans %= 1000000007;
ans *= ans;
ans %= 1000000007;
// 더 줄이는 것도 가능하다.
int ans;
for(int i = 0; i < 3; i++) {
ans *= 3;
ans %= 1000000007;
}
ans *= ans;
ans *= 3;
ans %= 1000000007;
ans *= ans;
ans %= 1000000007;
return 0;
}2. 재귀를 이용한 방법
#include <iostream>
using namespace std;
// 함수를 만든다.
int pows(int n, int m) {
if(m == 0) {
return 1;
}
int ret = pows(n, m / 2);
ret *= ret;
ret %= 100000000007;
if(m % 2 == 0) {
return ret;
} else {
return (ret * n) % 100000000007;
}
}
int main() {
cout << pows(3, 28);
return 0;
}+ Bouns
1. 1 ~ n 까지의 k배수의 개수
#include <iostream>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
cout << n / k;
return 0;
}2. 팩토리얼에 곱해진 소수의 개수
- p가 소수여야 가능한 방법
// n!를 p로 몇번 나눌 수 있는지
// p가 소수여야 가능한 방법
/// 20!에 곱해진 2의 개수
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
// 1 1 1 1 1 1 1 1 1 1
// 1 1 1 1 1
// 1 1
// 1
// 20// 2 + 20//4 + 20 // 8 + 20//16
// n// p + n//p^2 + n// p^3 + n// p^4....... 이므로...
#include <iostream>
using namespace std;
int main() {
int n, p;
cin >> n >> p;
int cnt = 0;
int x = p;
while (x <= n) {
cnt += n / x;
x *= p;
}
cout << cnt;
}- p가 소수가 아닌 경우
# 소수가 아닐 경우
# 20 에서 10인경우?
# 2 와 5 의 개수를 구한뒤, 최소개수를 답으로
# 20에서 20인경우?
# 2와 5의 개수를 구한 뒤, 2의 개수에 나누기 2를 한 뒤 최소개수를 답으로.'Develop > algorithm' 카테고리의 다른 글
| [알고리즘] 누적합 (Prefix Sum) (0) | 2024.01.26 |
|---|---|
| [알고리즘] 투 포인터 (Two pointer) (0) | 2024.01.18 |
| [알고리즘] 정수론 (0) | 2024.01.13 |
| [알고리즘] 재귀함수(recursion function) (0) | 2022.06.30 |
| [알고리즘] 투 포인터 (0) | 2022.06.30 |
