자바스크립트로 알고리즘 정리하기 #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();
});위에서 배운 이론을 그대로 코드로 구현만 하였다.
