[Algorithm] 정수론 - 유클리드 호제법, 에라토스테네스의 채, 이항 계수

정수론은 수학의 한 분야로서, 정수와 관련된 다양한 수학적 성질을 연구합니다. 이 분야는 기본적인 정수의 나눗셈부터 시작하여, 소수, 이차 형식, 다항식의 정수 해, 그리고 숫자의 분할과 같은 복잡한 주제까지 포괄합니다. 정수론은 수학 이론뿐만 아니라 컴퓨터 과학, 암호학, 그리고 수많은 응용 과학 분야에서도 중요한 역할을 합니다. 소수의 패턴, 정수들 사이의 관계, 그리고 숫자들의 이론적 특성을 탐구함으로써, 이 분야는 근본적인 수학적 이해를 제공합니다.

---

1. 유클리드 호제법

유클리드 호제법은 두 양의 정수의 최대공약수를 찾는 알고리즘입니다. 간단하면서도 매우 빠르게 최대공약수를 구할 수 있기 때문에, 컴퓨터 과학에서도 널리 사용되는 알고리즘 중 하나입니다.

구현 방식

• 두 수 a와 b (a > b)가 주어졌을 때, a를 b로 나눈 나머지를 r이라고 합니다.
• 이제 b와 r에 대해 같은 방법을 적용합니다.
• 이 과정을 반복하여 나머지가 0이 되었을 때, 마지막으로 나눈 수가 최대공약수가 됩니다.

예시

• 1071을 1029로 나누면 나머지는 42
• 1029를 42로 나누면 나머지는 21
• 42를 21로 나누면 나머지는 0
• 따라서 1071과 1029의 최대공약수는 21

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

---

2. 에라토스테네스의 채

에라토스테네스의 채는 소수를 찾는 방법 중 하나로, 고대 그리스 수학자 에라토스테네스가 고안한 방법입니다. 특정 범위 내의 모든 소수를 찾기 위해 사용되는 알고리즘입니다.

에라토스테네스의 채는 매우 간단하고 효율적인 방법으로, 특히 작은 수의 범위 내에서 소수를 찾을 때 유용합니다. 그러나 큰 수의 범위에 대해서는 메모리 사용량이 많아지고, 계산 시간도 길어질 수 있습니다.

구현 방식

• 초기화: 2부터 시작하여 특정 수 N까지의 모든 수를 나열합니다.
• 반복 과정: 가장 작은 수(초기에는 2)를 찾아 그 수의 배수를 모두 지웁니다. 이 때, 이미 지워진 수는 무시합니다.
• 배수 제거: 첫 번째 수(2)의 배수를 모두 지운 후, 다음으로 작은 수(이 경우 3)의 배수를 모두 지웁니다. 이 과정을 N의 제곱근까지 반복합니다.
• 결과: 남아 있는 수들이 바로 N 이하의 모든 소수입니다.

예시

• 2부터 10까지의 수를 나열합니다: 2, 3, 4, 5, 6, 7, 8, 9, 10.
• 가장 작은 수인 2의 배수(4, 6, 8, 10)를 모두 지웁니다.
• 다음으로 작은 수인 3의 배수(6, 9)를 지웁니다. 6은 이미 지워졌으므로, 9만 지웁니다.
• 10의 제곱근은 약 3.16이므로, 3 다음의 수인 5와 7은 체크할 필요가 없습니다.
• 남은 수(2, 3, 5, 7)가 10 이하의 소수입니다.

vector<int> sieve(int n) {
    vector<bool> prime(n + 1, true);
    prime[0] = prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    vector<int> primes;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            primes.push_back(p);
        }
    }
    return primes;
}

---

3. 이항 계수에 대한 설명

이항 계수는 조합론에서 중요한 개념으로, 'n개의 서로 다른 원소에서 k개를 선택하는 방법의 수'를 나타냅니다. 기호로는 $C(n, k)$ 또는 $\binom{n}{k}$로 표현되며, 다음과 같은 공식으로 계산됩니다:

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

여기서$n!$는 n의 팩토리얼을 의미합니다. 예를 들어, \( \binom{5}{2} \)는 5개의 원소 중 2개를 선택하는 조합의 수로, 다음과 같이 계산됩니다:

\( \binom{5}{2} = \frac{5!}{2! \times (5-2)!} = \frac{5 \times 4}{2 \times 1} = 10 \)

이 결과는 5개의 원소 중 2개를 선택하는 조합이 총 10가지임을 의미합니다.

$$ x=\frac{-b+\sqrt{b^{2}-4ac}}{2a} $$

 

구현 방식

1) 정의를 이용한 구현

이항 계수의 정의를 그대로 함수로 구현할 수 있습니다.

// 이항 계수를 계산하는 함수
long long binomialCoefficient(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

그러나 이 방식은 수 많은 재귀가 발생하며, 큰 수에 대한 계산에서는 오버플로우가 발생할 수 있으므로 주의해야 합니다.

2) 다이나믹 프로그래밍(DP)를 이용한 구현

이항 계수 \( C(n, k) \)를 계산하는 데 동적 계획법을 적용할 수 있습니다. 동적 계획법은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 방식입니다.

1. 2차원 배열 초기화: 크기가 \( n+1 \) X \( k+1 \)인 2차원 배열을 생성하고 모든 값을 0으로 초기화합니다.
2. 기저 사례 설정: \( C(n, 0) \)과 \( C(n, n) \)은 모두 1이므로, 배열의 첫 번째 열과 대각선을 1로 초기화합니다.
3. 동적 계획법 적용: 이제 점화식 \( C(n, k) = C(n-1, k-1) + C(n-1, k) \)을 사용하여 배열의 나머지 값을 채웁니다. 각 \( C(n, k) \)는 그보다 작은 두 이항 계수의 합으로 계산됩니다.
4. 결과 반환: 필요한 \( C(n, k) \) 값을 배열에서 찾아 반환합니다. 이 값은 입력된 n과 k에 대한 이항 계수의 정확한 값입니다.

이 방법은 중복 계산을 피하고, 이미 계산된 값을 재활용하기 때문에 매우 효율적입니다. 특히, 큰 값의 이항 계수를 계산할 때 유용합니다.

#include <iostream>
#include <vector>

// 이항 계수를 계산하는 함수 (DP 사용)
long long binomialCoefficient(int n, int k) {
    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(k + 1, 0));

    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1; // 모든 n에 대해 nC0 = 1
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= std::min(i, k); j++) {
            if (j == i || j == 0) {
                dp[i][j] = 1; // nCn과 nC0은 항상 1
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; // 점화식 적용
            }
        }
    }

    return dp[n][k];
}

int main() {
    int n, k;
    std::cout << "n과 k의 값을 입력하세요: ";
    std::cin >> n >> k;

    std::cout << "이항 계수 C(" << n << ", " << k << ") = " << binomialCoefficient(n, k) << std::endl;
    return 0;
}