알고리즘 풀이에 도움되는 수학 정리 !

알고리즘 풀이에 도움이 되는 수학을 정리하고자 글을 작성합니다! 
새로운 사실을 알 때마다 정리할 생각입니다 !
- update : 220527, 220531      

---

[ 정리 목록 ]

 

• 소수판별
• 좌표의 거리 구하기
• 소인수 분해
• 최대공약수(GCD)와 최소공배수(LCM) - feat. 유클리드 호제법
• 피보나치 수열
• 에라토스테네스의 체
• 골드바흐의 추측
•  

---

🤔 소수 판별

• 소수란 1과 자기 자산 외의 약수를 가지지 않는 1보다 큰 자연수입니다.
• 4 이상의 짝수는 무조건 소수가 아닙니다. (2의 배수이기 때문에)
• N이 소수가 아니라면 [ 2 ~ √N (루트 N) ] 범위에 약수가 무조건 존재합니다. 따라서 해당 범위에 약수가 없다면 N은 소수입니다.

function isPrime(num) {

    // 2,3 은 소수
    if (num <= 3) {
        return true;
    }
    // 2의 배수는 소수가 아님
    else if (num % 2 == 0) {
        return false;
    }

    // 2 ~ sqrt(num) 범위에서 num을 나누어 떨어지는 값이 있으면 소수가 아님
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

📌  4 미만의 자연수는 모두 소수이며, 4 이상의 짝수들은 무조건 소수가 아니며, 홀수들은 [ 2 ~ √N ] 범위까지에 약수가 존재하지 않으면 소수입니다.

 

 

🤔 좌표의 거리 구하기

• 좌표는 기본적으로 (x, y)로 구성됩니다. 
• 좌표 p1(x1, y1), p2(x2, y2) 사이의 거리는 D(p1, p2) = √ ( x1-x2)**2 + (y1-y2)**2) 입니다.
  최단거리같이 실제 거리를 구하지 않는 경우는 굳이 루트까지 계산해 줄 필요는 없습니다.

function getDistance(p1, p2) {
    // p1 = [0,3] 형식일 떄
    // p2 = [4,2] 형식일 떄

    let [x1, y1] = p1;
    let [x2, y2] = p2;

    // (x1 - x2) ** 2 + (y1 - y2) ** 2
    return Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2);
}

📌 두 점 p1(x1, y1), p2(x2, y2) 사이의 거리는 D(p1, p2) = √ ( x1-x2)**2 + (y1-y2)**2) 이며, 실제 거리를 구하는 문제가 아니면 굳이 루트까지 계산 해 줄 필요는 없습니다.

 

 

🤔 소인수 분해

• 소인수분해는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것을 말합니다.
• 소수는 소인수 분해의 결과가 자기 자신입니다. (ex. 7을 소인수 분해하면 = 7 임)
  따라서 N이 소수이면 [ 2~ sqrt(N) ]까지만 검사하고 끝날 것이며, 합성수이면 나누어 떨어지는 값(div)으로 N=N/div 으로 재할당하여 [ 2~ sqrt(N) ]검사를 다시 진행하는 방법으로 결과를 도출 할 수 있습니다.

function factor(num) {
    let factorArr = [];

    for (let div = 2; div <= Math.sqrt(num); div++) {
        /* div로 나누어 떨어지는 경우가 있다면
           소인수 분해 배열에 넣어주고, num을 div로 나눈 뒤 재 탐색
        */
        while (num % div == 0) {
            factorArr.push(div);
            num /= div;
        }
    }

    // N이 1이 아닌 다른수가 남아있는 경우 N은 소수임
    /*
    ex) 14를 예를 들면 
    
    [ 처음 반복 ]
    div = 2 일때 14%2= 0, 몫은 7 이므로 2 * 7 (N = N/2 = 7)

    [ 두번째 반복 ]
    div = 2 일때 7%2= 1 이므로 다음 탐색
    div = 3 일떄 N은 현재 7이므로 반복 조건에 맞지 않아 빠져나옴( 3<=sqrt(7), 3이 더 크기때문에 반복 종료 ) 
    따라서 반복 종료 시점에서 N = 7

    => 이처럼 검사 종료 후 N이 1이 아닌 경우는 소수인 경우 뿐임.
     */
    if (num > 1) {
        factorArr.push(num);
    }

    return factorArr.join(' * ');
}

📌 소인수 분해는 N을 [ 2~ sqrt(N) ] 검사하면서 나누어 떨어지는 값이 있으면 N을 그 값으로 나눈 값을 다시  [ 2~ sqrt(N) ] 검사하면서 반복 검사하면 됩니다. 검사 종료 후 N 값이 1보다 큰 경우는 N이 소수인 경우이기 때문에 조건 검사하여 1보다 크면 N 값을 소인수에 추가 시켜 줘야합니다.

 

 

🤔 최대공약수(GCD)와 최소공배수(LCM)

• 최대 공약수는 두 개 이상의 자연수의 공통인 약수 중에서 가장 큰 수를 의미합니다.
• 최소 공배수는 두 개 이상의 자연수의 공배수 중에서 가장 작은 수를 의미합니다.
• 최대 공약수는 유클리드 호제법을 통해 구할 수 있습니다.
• 최소 공배수는 ( 두 수의 곱/최대 공약수 ) 입니다.

* 유클리드 호제법 ?
- 2개의 자연수의 최대 공약수를 구하는 알고리즘의 하나 입니다.
- 시간 복잡도는 O(logN) 입니다.

[풀이 단계]
1. 큰 수를 작은수로 나눈 나머지를 구합니다. (MOD 연산)
2. 나머지가 0이 아니라면, 나눴던 수(작은 수)와 나머지의 MOD 연산을 합니다.
3. 위 과정을 반복하며 나머지가 0일 때 나누는 수로 사용된 값이 최대 공약수 입니다.

/* [최대 공약수 구하기]
 a가 b로 나누어 떨어지면 b가 최대 공약수
 그렇지 않다면? b와 (a%b)의 최대 공약수가 전채의 최대공약수가 된다.
*/

// 반복문으로 구현
function getGCD1(A, B) {
    while (A % B != 0) {
        let C = A % B;
        A = B;
        B = C;
    }
    return B
}

// 재귀함수로 구현 & 일반 함수
function getGCD2(A, B) {
    if (A % B == 0) {
        return B;
    } else {
        return getGCD2(B, A % B);
    }
}

// 재귀함수로 구현 & 화살표 함수
const getGCD3 = (A, B) => A % B == 0 ? B : getGCD3(B, A % B);

/* [최소 공배수 구하기]
 두 수의 최소공배수는
 두 수의 곱/두 수의 최대공약수 와 같다.
*/

let A = 75221805;
let B = 105181189;
const getGCD3 = (A, B) => A % B == 0 ? B : getGCD3(B, A % B);

let getLCM = A * B / getGCD3(A, B);

console.log(getLCM) // = 1345793313255

📌 최대 공약수는 ( 유클리드 호제법 )을 통해서 구할 수 있습니다. 최소 공배수는 ( 두 수의 곱/최대 공약수 ) 입니다.

 

 

🤔 피보나치 수열

• 피보나치 수열이란 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열입니다.
  ex) 1, 1, 2, 3, 5, 8 ..  (편의상 0번째 항을 0으로 두기도 함)
• 재귀 함수 혹은 배열을 통한 점화식으로 구현 할 수 있습니다. 

* 점화식(재귀식, 수열의 귀납적 정의) ?
- 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식입니다.

// 재귀 함수로 구현
function getFibo1(nIdx) {
    if (nIdx < 2) {
        return 1;
    } else {
        return (getFibo1(nIdx - 1) + getFibo1(nIdx - 2));
    }
}

// 배열을 통한 구현 (점화식)
function getFibo2(nIdx) {

    if (nIdx == 0 || nIdx == 1) return 1;

    let fib = [1, 1];
    for (let i = 2; i <= nIdx; i++) {
        fib.push((fib[i - 1] + fib[i - 2]));
    }

    return fib[nIdx];
}

📌 피보나치 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로, 재귀 함수 혹은 배열을 이용한 점화식을 통해 구현합니다.

 

 

🤔 에라토스테네스의 체

• 에러토스테네스의 체는 특정 숫자의 배수는 소수가 아니라는 법칙에 의해 2 ~ N 까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식입니다. 특히 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우에 사용하기 좋은 알고리즘입니다.
• [ 2  ~ √N ] 까지의 특정 숫자의 제곱근까지 약수의 여부를 검증하면 시간 복잡도는 O(N**1/2)  의 시간 복잡도를 가집니다. 

function fillSieve(N) {

    /*
    idx와 숫자를 매칭시키기 위해 N+1 만큼 해줌 (인덱스 번호가 주어진 숫자 n과 대응하도록)
    0 ~ N값 배열에 초기화, 즉 [0,1,2,3,4,5, ~ N]
    => ex) 숫자 1의 소수 여부값이 isPrime[1]에 저장
     */
    let isPrime = Array.from({ length: N + 1 }, (dr, idx) => idx);

    isPrime[1] = 0; // 1은 소수가 아니므로 0으로

    for (let num = 2; num <= N; num++) {

        // 현재 값이 소수가 아니면 continue
        if (isPrime[num] == 0) {
            continue;
        }

        /*
        현재 값이 소수이면 해당 값의 제곱부터 ~ 그 값에서 num의 배수를 체크
        => ex) i가 7 일 때, 7의 제곱 수 49 이전의 7의 배수들은 이미 앞에서 소수체크가 된 상태
               즉 14, 21, 28.. 값들은 이미 지워진 상태 !
         */
        for (let i = num * num; i <= N; i += num) {
            isPrime[i] = 0;
        }
    }

    // 검사 후 0이 아닌 값들은 소수임 !
    return isPrime.filter((dr) => dr != 0).join(', ');
}

console.log(fillSieve(37));
// = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 이 나옴!

📌 에라토스테네스의 체는 특정 범위에서 소수를 찾는데, 좋은 효율을 보이는 알고리즘입니다. [ 2  ~ √N ] 까지의 수를 검증하면서 소수인 숫자들의 배수를 모두 제거한 뒤 남은 숫자를 소수로 판별합니다.  

 

 

🤔 골드바흐의 추측

• 골드바흐의 추측이란 "4보다 큰 모든 짝수 자연수는 홀수인 두 소수의 합으로 표현 가능하다" 라는추측입니다. 두 소수를 구하기 위해서는 [ 3 ~ N/2 ] 범위를 +2 씩 증가하는 값을 p라고 가정했을 때, ( p, N-p )두 값이 모두 소수인지 체크하여 구합니다. 
• ( p, N-p ) 두 값을 계속해서 소수인지 체크하는 것 보다 에라토스테네스의 체를 이용하여  [ 1 ~ N ] 범위의 홀수 여부를 체크하는 배열을 만들어 ( p, N-p ) 두 인덱스의 값이 모두 홀수일 때 정답을 도출하는 것이 효율적입니다.

function fillSieve(N) {

    let isPrime = Array.from({ length: N + 1 }).fill(true);

    // 0, 1 은 소수가 아님.
    isPrime[0] = false;
    isPrime[1] = false;

    for (let num = 2; num <= N; num++) {

        if (isPrime[num] == false) {
            continue;
        }

        for (let i = num * num; i <= N; i += num) {
            isPrime[i] = false;
        }

    }

    // 소수인 값은 true, 소수가 아니면 false를 가지는 배열
    return isPrime;
}

function solution(N) {

    // 1~N 까지 소수 여부를 저장하는 배열
    let fillArr = fillSieve(N);

    /*
    [ 3 ~ N/2 ] 범위를 반복하며 ( p, N-p ) 두 값이 소수 인지를 체크
    N/2 범위까지 하는 이유는 더 이상 넘어가면 앞에서 검사한 수와 동일하기 때문!!
    => ex) N = 12 일때 검사하는 두 수는 (3,9) (5,7) (7,5) (9,3)
           위 예시처럼 6을 넘어가면 앞에서 검사한 중복 된 수를 검사함!
     */
    for (let p = 3; p <= N / 2; p += 2) {
        let q = N - p;

        // p && q 가 모두 소수이면 정답!
        if (fillArr[p] && fillArr[q]) {
            return [p, q]
        }
    }

    return -1;
}

console.log(solution(42));
// [5, 37]

📌 골드바흐의 추측은 "4보다 큰 모든 짝수 자연수는 홀수인 두 소수의 합으로 표현 가능하다" 라는 추측입니다. 두 수를 구하기 위해서는 에라토스테네스의 체를 이용하여 [ 1~N ]까지의 소수 여부를 가지는 배열을 구한 후 배열에서 ( p, N-p ) 두 값이 모두 소수여부가 참이면 정답을 도출 할 수 있습니다.