프로그래머스 알고리즘 수학 [LV 1]

 

1. 가우스의 덧셈 공식 (등차수열의 합)

// 가우스 덧셈 공식(Gauss's trick)
// 1부터 n까지의 합을 구할 때 (1 + n) * n / 2

// 예: price만큼 배수로 늘어나는 이용료를 count번 탔을 때 총합
// (첫 번째 수 + 마지막 수) × 개수 / 2
function getSum(price, count) {
    const start = price;        // 첫 번째 수
    const end = price * count;  // 마지막 수
    
    return (start + end) * count / 2;
}

 

2. 유클리드 호제법 (GCD / LCM)

// 최대공약수(Greatest Common Divisor)
// A를 B로 나눈 나머지를 r이라고 할 때, GCD(A, B) = GCD(B, r) (나머지가 0이 될 때까지 반복)
const getGCD = (a, b) => (b === 0 ? a : getGCD(b, a % b));

// 최소공배수(Least Common Multiple)
// (A × B) ÷ GCD
const getLCM = (a, b) => (a * b) / getGCD(a, b);

 

3. 제곱근 판별법

// 약수의 개수가 홀수(제곱수)인지 판별
// 정수이면 제곱수(=약수 홀수개), 아니면 일반 수(=약수 짝수개)
if (Number.isInteger(Math.sqrt(num))) {
    // 제곱수입니다!
}

// 소수 판별하기 (일반적인 방법)
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;
}

// 에라토스테네스의 채
// 소수 빠르게 판별하기 (시간 초과 문제 발생시)
const arr = Array(n + 1).fill(true);
arr[0] = false; arr[1] = false;

for (let i = 2; i <= Math.sqrt(n); i++) {
    if (arr[i]) {
        // i의 배수들을 싹 다 지움 (i * i 부터 시작)
        for (let j = i * i; j <= n; j += i) {
            arr[j] = false;
        }
    }
}