자바스크립트로 알고리즘 문제 풀때 유용한 수학 공식

자바스크립트 알고리즘 문제 풀이에 자주 사용되는 수학 공식 모음

알고리즘 문제를 풀 때 자주 활용되는 기본적인 수학 공식들을 JavaScript로 구현해보았습니다. 코딩 테스트나 알고리즘 학습에 도움이 되길 바랍니다.

1. 최대공약수 (GCD)

유클리드 호제법을 이용한 최대공약수 계산 방법입니다. 두 수의 최대공약수를 구하는 가장 효율적인 방법 중 하나입니다.

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

2. 최소공배수 (LCM)

두 수의 최소공배수를 구하는 공식입니다. GCD를 활용하여 계산합니다.

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

3. 소수 판별

주어진 숫자가 소수인지 판별하는 함수입니다. 최적화를 위해 제곱근까지만 확인합니다.

function isPrime(num) {
    if (num < 2) return false;
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) return false;
    }
    return true;
}

4. 팩토리얼

재귀를 사용한 팩토리얼 계산 함수입니다.

function factorial(n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}

5. 순열

순열의 수를 계산하는 함수입니다.

function permutation(n, r) {
    return factorial(n) / factorial(n - r);
}

6. 조합

조합의 수를 계산하는 함수입니다.

function combination(n, r) {
    return factorial(n) / (factorial(r) * factorial(n - r));
}

7. 피보나치 수열

반복문을 사용한 효율적인 피보나치 수열 계산 방법입니다.

function fibonacci(n) {
    if (n <= 1) return n;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
}

8. 제곱근 계산

바빌로니아 방법을 사용한 제곱근 계산 함수입니다.

function sqrt(n) {
    let x = n;
    let y = 1;
    const e = 0.000001; // 오차 허용 범위
    while (x - y > e) {
        x = (x + y) / 2;
        y = n / x;
    }
    return x;
}

활용 팁

위의 수학 공식들은 다음과 같은 상황에서 특히 유용합니다:

• GCD와 LCM은 분수 계산이나 약수/배수 관련 문제에서 자주 사용됩니다.
• 소수 판별 함수는 암호화나 정수론 관련 문제에서 필수적입니다.
• 순열과 조합은 경우의 수를 계산하는 문제에서 활용됩니다.
• 피보나치 수열은 동적 프로그래밍 문제의 기초가 됩니다.
• 제곱근 계산은 기하학 관련 문제에서 유용합니다.

이러한 기본적인 수학 공식들을 잘 이해하고 있으면 알고리즘 문제 해결에 큰 도움이 될 것입니다. 실제 문제에 적용할 때는 문제의 제약 조건과 요구사항을 잘 고려하여 적절히 수정하여 사용하시기 바랍니다.

---