알고리즘 학습

학습 노트

Priority Queue

1. 비교연산자 : struct cmp 안에 operator() 함수 만들어서 사용

struct cmp{
    bool operator()(int t, int u){
        return t < u;
    }
};

priority_queue<int, vector<int>,cmp> pq;

비트 연산자

1. a&-a : 비트 1 중에서 최하위 비트 한개만 남긴다.
   • 1 -> 1
   • 2 -> 2
   • 3 -> 1
   • 4 -> 4
   • 5 -> 1
   • 6 -> 2
   • 7 -> 1
   • 8 -> 8 이를 활용해서 인덱스 트리 연산을 효율적으로 구할 수 있다.

자잘한 것들

1. 스트링 printf 출력 방법: scanf("%s", str.c_str());
2. printf float은 소수점 반올림해서 출력한다.

정수론

합동식

a ≡ b (mod p) 는 a를 p로 나눈 나머지가 b를 p로 나눈 나머지와 같다는 뜻이다.

1. a ≡ b (mod p) => b ≡ a(mod p)
2. a ≡ b (mod p), b = c (mod p) => a ≡ c(mod p)
3. a ≡ b (mod p) => ac ≡ bc (mod p)
4. a ≡ b (mod p) => a+c = b+c (mod p)
5. ac ≡ bc (mod p) !=> a ≡ b (mod p)
6. ac ≡ bc (mod p) => a ≡ b (mod p/gcd(c,p))

유클리드 호제법

두 자연수 a,b의 최대 공약수는 a를 b로 나눈 나머지 r과 b의 최대공약수와 같다. 그러므로 gcd(a, b) == gcd(a%b, b)이다.

확장 유클리드 호제법

• 부정 방정식 : 해가 무수히 많은 방정식.
• 디오판포스 방정식 : 해가 정수인 경우의 부정 방정식
• 베주 항등식 : 정수 a,b의 최대 공약수를 gcd(a,b)로 나타낼 때, 확장 유클리드 호제법을 이용하여 ax + by = gcd(a,b)의 해가 되는 정수 x, y 짝을 찾아낼 수 있다. 이식을 베주의 항등식이라고 한다.

관련 문제: 백준 3955번 캔디 분배

에라토스테네스의 체

소수를 찾는 알고리즘

for(int i=2;i<=numbers.size();i++) {
   if(numbers[i]==0) continue;
   for(int j=2*i;j<=number; j+=i) {
       numbers[j] = 0;
   }

조합론

순열과 조합

1. 순열 : n가지의 물건 중 k개의 물건을 순서 구분하여 고르는 경우의 수

    nPk = N! / (N-K)!

2. 중복 순열: n가지의 물건 중 중복을 허용하여 k개의 물건을 순서있게 고르는 경우의 수
    
    nΠk = N^k

3. 다중집합의 순열: n가지의 물건 중 같은 물건이 가각 p,q,r개 일때, n개의 물건을 모두 택하여 순서 있게 고르는 경우의 수

    N! / p!q!r!

4. 원순열: N가지의 물건 중 K개의 물건을 원형으로 배열하는 경우의 수
    
    nPk/K = N!/ K(N-K)!

5. 조합: N가지의 물건 중 K개의 물건을 순서 구분 없이 고르는 경우의 수

    nCk = nPk/K! = N!/K!(N-K)!

6. 중복조합: N가지의 물건 중 중복을 허용하여 K개의 물건을 순서 구분 없이 고르는 경우의 수

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

파스칼의 삼각형

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

메모이제이션을 사용한다면(n^2) 일일이 nCk를 구하는 것(n!)보다 훨씬 빠르게 조합값을 구할 수 있다. n!를 계산하는 것은 또한 자료형의 범위를 넘어갈 수도 있다.(15! > 2^32-1, 21! > 2^64-1)

또한 이항정리에서도 사용가능하다.