수학

https://www.youtube.com/watch?v=2RCJApSVxRI

n이 소수인지 판정하는 함수

bool isPrime(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

범위를 i<=n-1로 하는 것은 비효율적이기에 저렇게 한다.

 

범위 내에서의 소수 판정 - 에라토스테네스의 체

vector<int> seive(int n){
    vector<int> primes;
    vector<bool> state(n+1,true);
    state[1]=false; //1은 소수 아님
    for(int i=2;i*i<=n;i++){
        if(!state[i]) continue; //이미 소수로 판별되었으면 continue
        for(int j=i*i;j<=n;j+=i){ //소수인 수의 배수를 false로 체크한다.
            //범위가 i*i부터인 것은 앞에서 한 번 걸러졌을 것이기 때문이다.
            state[j]=false;
        }
    }
    for(int i=2;i<=n;i++){
        if(state[i]) primes.push_back(i);
    }
    return primes;
}

전에 이 알고리즘을 써야 할 일이 있어서 찾아봤는데 잘 이해가 안됐다. 이 강의를 보면서 동작을 완전히 이해할 수 있었다.

http://boj.kr/d9c2e56f015444dd87ec6b614fbcbf33

 

소인수분해

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;

    for(int i=2;i*i<=n-1;i++){
        while(n%i==0){
            cout<<i<<'\n';
            n/=i;
        }
    }
    if(n!=1) cout<<n;
    
    return 0;
}

마지막 남은 수가 소수일 경우엔 if문을 통해 출력하게 해준다.

 

최대공약수 - 유클리드 호제법

두 수 A, B에 대해 A를 B로 나눈 나머지를 r이라고 하면 GCD(A,B)=GCD(B,r) 이다.(Greatest Common Divisor: 최대공약수 - 두 자연수의 공통된 약수 중 가장 큰 약수)

 

왜 그런지는 복잡히니 pass하고 재귀를 이용해 이를 간단히 구현할 수 있다.

int gcd(int a, int b){
    if(a==0) return b;
    return gcd(b%a,a);
}

C++17부터는 numeric에 gcd가 이미 존재한다고 한다.

 

최소공배수

A x B = GCD(A,B) x LCM(A,B)

GCD를 이용하면 LCM도 구할 수 있다.

int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

 

연립합동방정식

1부터 29까지 돌면서 확인할수도 있지만 6으로 나눈 나머지가 3인 경우만 살피면서, 5로 나눈 나머지가 2인 수를 구하면 더욱 효율적이다.

int chk(){
    for(int i=3;i<30;i+=6){
        if(i%5==2) return i;
    }
    return -1;
}

 

연립합동방정식

순열 순서 고려

조합 순서고려X

 

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

nCk = (n-1)C(k-1) + (n-1)C(k)

//https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/11051.cpp
// http://boj.kr/4d33c0a441344bf0b631fdbf7825a7c2
#include <bits/stdc++.h>
using namespace std;

int comb[1002][1002];
int mod = 10007;
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  for(int i = 1; i <= 1000; i++){
    comb[i][0] = comb[i][i] = 1;
    for(int j = 1; j < i; j++)
      comb[i][j] = (comb[i-1][j] + comb[i-1][j-1])%mod;
  }
  int n, m;
  cin >> n >> m;
  cout << comb[n][m];
}

 

글 내용은 모두 [바킹독의 실전 알고리즘] 0X12 - 수학을 듣고 정리한 것입니다