수학

수학

소수

• 소수: 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