조합론과 수론은 알고리즘 문제 해결에서 중요한 역할을 한다. 여기에서는 이 분야의 핵심적인 개념들과 이를 활용한 몇 가지 기법들을 다룬다.

조합론

가법 원리와 곱셈 원리

가법 원리에 따르면, 어떤 일을 수행하는 두 가지 방법이 있을 때 첫 번째 방법으로는 a개의 방법이 있고, 두 번째 방법으로는 b개의 방법이 있다면 총 a+b개의 방법으로 일을 완수할 수 있다. 곱셈 원리는 서로 다른 두 단계로 이루어진 일이 있을 때 각 단계마다 a와 b개의 방법이 있으면 총 a*b개의 방법으로 일을 완성할 수 있다는 것이다.

순열과 조합

n명의 사람이 있는 그룹에서 가능한 모든 배열 방법은 n!이다. 만약 m명을 선택한다면, 이를 나타내는 공식은 C(n, m) = n! / (m!(n-m)!)이다. 이 경우를 기반으로 m명을 선택하여 줄을 세우는 방법은 A(n, m) = n! / (n-m)!로 표현된다.

카탈란 수

n개의 노드로 구성된 서로 다른 이진 트리의 개수를 나타내는 카탈란 수는 아래와 같은 점화식으로 계산될 수 있다: C(n) = Σ(C(i) * C(n-i-1)) for i=0 to n-1. 더 간단히 표현하면 C(n) = (2n)! / ((n+1)!n!)이다.

수론

최대 공약수와 최소 공배수

두 정수 a와 b의 최대 공약수를 구하는 유클리드 알고리즘은 gcd(a, b) = gcd(b, a mod b)를 이용한다. 또한 lcm(a, b) * gcd(a, b) = a * b임을 알 수 있다.

확장 유클리드 알고리즘

정수 a, b, c가 주어질 때 xa + yb = c를 만족하는 정수 해 x와 y를 찾는 문제는 확장 유클리드 알고리즘을 통해 해결할 수 있다. 이를 위해 d = gcd(a, b)라고 할 때 c가 d의 배수가 아니면 해는 존재하지 않는다.

역원

모듈러 산술에서 b의 역원은 b^-1 * b ≡ 1 (mod m)을 만족하는 값이다. 이 역원은 b와 m이 서로소일 때만 존재하며, 이를 확장 유클리드 알고리즘을 통해 구할 수 있다.

코드 예제

역원 계산

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

long long mod_pow(long long base, long long exp, long long mod_val) {
    long long result = 1;
    while(exp > 0){
        if(exp % 2 == 1){
            result = (result * base) % mod_val;
        }
        base = (base * base) % mod_val;
        exp /= 2;
    }
    return result;
}

int main(){
    long long a, p;
    cin >> a >> p;
    if(__gcd(a, p) != 1){
        cout << "역원이 없습니다.";
        return 0;
    }
    long long inv = mod_pow(a, p-2, p);
    cout << inv;
}

확장 유클리드 알고리즘

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

void ext_gcd(long long a, long long b, long long &x, long long &y){
    if(b == 0){
        x = 1; y = 0;
        return;
    }
    ext_gcd(b, a % b, x, y);
    long long temp = x;
    x = y;
    y = temp - (a / b) * y;
}

int main(){
    long long a, b, c;
    cin >> a >> b >> c;
    long long x, y;
    ext_gcd(a, b, x, y);
    if(c % __gcd(a, b) != 0){
        cout << "-1";
        return 0;
    }
    x *= c/__gcd(a, b);
    cout << x;
}