자바스크립트로 알고리즘 정리하기 #6 수학1 (나머지 연산, 최대 공약수)

Jake Seo·2020년 9월 1일

javascript-algorithm

목록 보기

6/11

자바스크립트로 알고리즘 정리하기 #6 수학 (나머지 연산, 최대 공약수)

나머지 연산 개념

나머지 연산이 사용되는 경우는 '큰 수의 정답을 x로 나눈 나머지를 출력하시오.' 와 같은 경우에 쓰이게 된다. 정답을 구하는 것이 실상 중요하고, 자릿수의 크기는 중요하지 않을 때 많이 쓰인다.

나머지 연산의 법칙

일반적으로 자릿수에 제한이 있는 경우에는 정답을 구한 이후에 딱 한번 나머지 연산을 하지 않고, 정답을 구할 때마다 매번 나머지 연산을 수행해주어야 한다.

이렇게 매번 나머지 연산을 해도 되는 이유는

(A+B) % M = ((A % M) + (B % M)) % M 과 같은 수식이 성립하기 때문이다.
(A*B) % M = ((A % M) * (B % M)) % M 과 같은 수식도 성립한다.

단, 나누기의 경우에는 성립하지 않는다. Modular Inverse를 구해야 한다.

뺄셈의 경우에는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에

(A-B) % M = ((A % M) - (B % M)+M) % M 과 같이 해주어야 한다.

덧셈

간단히 A와 B가 5일 때 테스트 해보면,

(5+5) % 3 = 1 인데,
(5%3) + (5%3) = 4이고 4%3 = 1이 나온다.

곱셈은 더하기의 연속이기 때문에 성립한다.

뺄셈

뺄셈의 경우에는 음수가 나왔을 때 약간 애매한데, A가 6이고, B가 5일 때, (6-5)%3=1이다.

그런데 (6%3 - 5%3) % 3 = (0-2) % 3 = -2 % 3 = ? -2를 3으로 나눈 나머지는 몇일까?

이 경우에는 프로그래밍 언어에 따라 결과가 약간 다르다. C, C++, JAVA에서는 -2가 나온다. python3의 경우 1이 나온다.

이런 경우를 방지하기 위해서, 나머지를 더하고 다시 나머지 연산을 하는 경우가 있다.

0 <= a%c < c, 0 <= b%c < c 이기 때문에 (a%c - b%c)의 결과는 -c<(a%c - b%c)<c를 만족한다.

따라서, (a%c - b%c + c)는 0보다 큰 값을 갖기 때문에, 이 상태에서 다시 c로 나눠주면 원하는 결과를 얻을 수 있다.

결국 앞의 수식에 c를 더해주고 다시 c를 나눠주는 것이다.

최대공약수 개념

최대공약수는 줄여서 GCD라고 쓴다.
최대공약수는 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다.
최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어보는 방법이다.
최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.

최대공약수 구하기 구현

let getGCD = (a, b) => {
    let gcd = 1;

    for(let i=2; i<=Math.min(a, b); i++){
        if(a % i === 0 && b % i === 0){
            gcd = i;
        }
    }

    return gcd;
}

위의 방법은 O(N)의 시간복잡도에 최대공약수를 구할 수 있다.

유클리드 호제법을 이용한 구현

유클리드 호제법의 기본 원리는 a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) = GCD(b, r)과 같다는 것이다.

r이 0이라면, 그 때의 b가 최대공약수이다.

a=24, b=16을 가정하면, GCD(24, 16) = GCD(16, 8) = GCD(8, 0)

GCD = 8

let getGCD = (a, b) => (b > 0 ? getGCD(b, a % b) : a);

a < b의 경우에는 값이 자동스왑된다. ex) a=16, b=24일 경우에는 getGCD(24, (16%24=16))이 불러지게 된다.

재귀를 안쓰고 구현하면

let getGCD2 = (a, b) => {
  
    while(b > 0){
        let r = a % b;
        a = b;
        b = r;
    } 

    return a;
}

위와 같이 구현될 수 있다.

시간복잡도는 O(logN)이 나온다.

최소공배수 개념

최소공배수는 줄여서 LCM이라고 한다.
두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수를 말한다.
최소공배수는 위에서 구했던 GCD(최대 공약수)를 응용해서 구할 수 있다.
두 수 a, b의 최대공약수를 gcd라고 했을 때, 최소공배수 lcm = gcd * (a/gcd) * (b/gcd) 이다.
a * b = gcd * lcm 과 같다는 원리를 이용하는 것이다.
lcm = (a*b) / gcd 이다.

boj 2609 GCD, LCM 연습문제

문제 링크

let getGcd = (a, b) => (b > 0 ? getGcd(b, a % b) : a);
let getLcm = (a, b, gcd) => (a * b) / gcd;
let solution = (line) => {
  const [a, b] = line.split(' ').map((e) => +e);
  let gcd = getGcd(a, b);
  return gcd + '\n' + getLcm(a, b, gcd);
};

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', function (line) {
  console.log(solution(line));
  rl.close();
}).on('close', function () {
  process.exit();
});