수학
수학
소수
- 소수: 1과 자기 자신으로만 나누어지는 수
- 합성수 N에서 1을 제외한 가장 작은 약수는 √n 이하
- 범위 내에서의 소수 판정법: 에라토스테네스의 체
- 소인수분해: 2부터 계속 나누기(더이상 나누어지지 않는다면 1씩 증가시키면서 나누기)
// 시간복잡도: O(N) bool isprime(int n){ if(n==1){ return 0; } for(int i=2;i<n;i++){ if(n%i==0){ return 0; } } return 1; } // 시간복잡도: O(√n) bool isprime(int n){ if(n==1){ return 0; } for(int i=2;i*i<=n;i++){ if(n%i==0){ return 0; } } return 1; }
// 에라토스테네스의 체 // 시간복잡도: O(NlglgN) // Tip: vector<bool>로 사용하면 bool 한 칸이 1byte가 아니라 1bit를 차지하여(최적화가 일어남) 공간을 8배 적게 사용하고 cache hit rate도 올라가서 시간도 빨라짐 #include<iostream> #include<vector> using namespace std; vector<int> isprime(int n){ vector<int> primes; vector<bool> state(n+1, true);// vector<bool>로 사용하면 bool 한 칸이 1byte가 아니라 1bit를 차지하여 공간을 8배 적게 사용하고 cache hit rate도 올라가서 시간도 빨라짐 state[1]=false; for(int i=2;i*i<=n;i++){ if(!state[i]){ continue; } for(int j=i*i;j<=n;j+=i){ state[j]=false; } } for(int i=2;i<=n;i++){ if(state[i]){ primes.push_back(i); } } return primes; } int main(void){ return 0; }
최대공약수
- 약수: 어떤 수를 나누어 떨어지게 하는 수
- 최대공약수(Greatest Common Divisor): 두 자연수의 공통된 약수 중 가장 큰 약수
- 유클리드 호제법: 두 수 A,B에 대해 A를 B로 나눈 나머지를 r이라고 하면 GCD(A,B)=GCD(B,r)이다.
- ex) GCD(20,12)=GCD(12,8)=GCD(8,4)=GCD(4,0)=4
- 최소공배수: GCD(A,B)LCM(A,B)=AB
// 약수 구하기 #include<iostream> #include<vector> using namespace std; vector<int> divisor(int n){ vector<int> div; for(int i=1;i*i<=n;i++){ if(n%i==0){ div.push_back(i); } } // int 형변환의 이유? // vector의 size는 unsigned를 반환함 따라서 0-1은 -1이 아니라 2^32-1을 가짐 for(int j=(int)div.size()-1;j>=0;j--){ if(div[j]*div[j]==n){ continue; } div.push_back(n/div[j]); } return div; } int main(void){ return 0; }
// 최대공약수 구하기 int gcd(int a,int b){ if(a==0){ return b; } return (b%a,a); } // 최소공배수 구하기 // 먼저 나눈 이유는 a*b로 인한 int overflow 방지 int lcm(int a,int b){ return a/gcd(a,b)*b; }
연립합동방정식
- 1개 기준을 잡고 나머지로 체크
// 6명씩 조를 짰을 때 3명이 남음 // 5명씩 조를 짰을 때 2명이 남음 // 학생은 30명 미만 int chk(){ for(int i=3;i<30;i=i+6){ if(i%5==2){ return i; } } return -1; }
이항계수
- 조합(nCk): 순서를 고려하지 않고 5개에서 3개를 뽑는 경우의 수: 5!/(3!2!)=10
- 순열(nPk): 순서를 고려해 5개에서 3개를 뽑는 경우의 수: 5!/2!=60
- nCk = n-1Ck + n-1Ck-1