자바스크립트로 알고리즘 정리하기 #8 수학 연습문제
GCD 합 (boj 9613)
최대공약수를 구해서 그 합을 도출하면 된다.
let getGcd = (a, b) => (b > 0 ? getGcd(b, a % b) : a);
let solution = (input) => {
let answer = [];
for (let i = 1; i < input.length; i++) {
let sum = 0;
let line = input[i].split(' ');
for (let j = 1; j < line.length; j++) {
for (let k = j + 1; k < line.length; k++) {
sum += getGcd(+line[j], +line[k]);
}
}
answer.push(sum);
}
return answer.join('\n');
};
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on('line', function (line) {
input.push(line);
}).on('close', function () {
console.log(solution(input));
process.exit();
});
/*
Test Case 1:
let test = `3
4 10 20 30 40
3 7 5 12
3 125 15 25`;
console.log(solution(test.split('\n')));
*/숨바꼭질 6 (boj 17087)
일직선 상에 수빈이와 동생이 널부러져있다. 수빈이가 동생에게 가려면 걸음 폭이 얼만큼 되어야 하는지를 구하는 문제이다.
입력이
3 3
1 7 11이라고 주어지면
차례로
N S
A1 A2 A3를 의미한다.
3(동생 수) 3(수빈의 위치)
1 7 11(각 동생의 위치)위의 경우에는 수빈은 2씩 움직이는 것이 최대값이다.
1씩 움직이면 모든 동생에게 닿을 수 있지만, 최대값이 아니다.
2씩 움직이면 모든 동생에게 닿을 수 있고, 최대 값이다.
3씩 움직이면 모든 동생에게 닿을 수 없다.
3씩 움직인다고하면 수빈이가 갈 수 있는 곳은 0 3 6 9 12 이기 때문이다.
3 81
33 105 57위 예제를 보면 24씩 움직이는 것이 최대이다.
결과적으로 이 문제에서는 수빈이가 움직여야 하는 모든 거리를 구하고 그것의 최대공약수를 구하면 된다. 모든 거리차이를 이용하여 최대공약수를 만들면, 모든 동생과의 거리차이 X를 만들어낼 수 있다.
결국 모든 거리차이를 만들어낼 수 있는 수를 찾는게 핵심이다.
let getGcd = (a, b) => (b > 0 ? getGcd(b, a % b) : a);
let solution = (input) => {
const [n, s] = input[0].split(' ').map((e) => +e);
let a = input[1].split(' ').map((e) => +e);
a = a.map((e) => Math.abs(s - e));
let answer = getGcd(a[0], a[1] || 0);
for (let i = 2; i < a.length; i++) {
answer = getGcd(answer, a[i]);
}
return answer;
};
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on('line', function (line) {
input.push(line);
}).on('close', function () {
console.log(solution(input));
process.exit();
});위와 같은 방식으로 풀었다. 결국에는 공통적인 최대공약수를 구하는게 핵심
골드바흐 파티션 (boj 17103)
이전에 풀었던 골드바흐 문제를 약간 꼬아놓은 것인데,
에라토스테네스의 체 만들고, 소수의 합으로 n이 만들어지는 경우에 카운트하면 된다.
그런데 a + b = c 일 때 a, b의 위치가 바뀌는 것은 같은 경우로 치라고 했으니까,
다루는 소수의 범위를 n/2 까지만 연산해주고 break 해준다.
let erathos = (n) => {
let sieve = new Array(n + 1).fill(true);
sieve[0] = false;
sieve[1] = false;
/* 에라토스테네스의 체 - 배수로 만들어지는 것들 전부 지운다. */
for (let i = 2; i <= n; i++) {
if (sieve[i]) {
for (let j = i + i; j <= n; j += i) {
sieve[j] = false;
}
}
}
// 소수 보기
// sieve.map((e, i) => (e ? console.log(i) : ''));
return sieve;
};
let sieve = erathos(1000000);
let goldBachPartition = (n) => {
let count = 0;
for (let i = 0; i < sieve.length; i++) {
if (i > n / 2) {
break;
}
if (sieve[i]) {
if (sieve[n - i]) {
count++;
}
}
}
return count;
};
let solution = (input) => {
let answer = [];
for (let i = 1; i < input.length; i++) {
answer.push(goldBachPartition(input[i]));
}
return answer.join('\n');
};
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on('line', function (line) {
input.push(line);
}).on('close', function () {
console.log(solution(input));
process.exit();
});
소인수분해 (boj 11653)
기본 아이디어로 숫자를 1씩 증가시키면서 나눠떨어지는 것들을 반복해서 모으면 된다. 그런데 시간을 최적화하는 핵심은 이러한 짓을 루트n까지만 하면 된다는 것이다.
그 이유는 ...
예전에 배웠던 알고리즘 중에 소수를 구하는 알고리즘이 있었는데, 만일 N이 소수가 아니라면 자기 자신 이외의 자연수의 곱으로 표현이 가능한 것이니까 a*b의 형태로 표현이 가능할 것이다. N이 a와 b의 곱으로 표현 가능할 때, a와 b의 차이가 가장 최소가 될 때는 루트 n * 루트n 일 것이다.
이러한 원리를 다시 되새겨서 생각해보면, 만일 제곱근보다 큰 약수가 나온다면, 그 약수로 나눈 몫은 제곱근보다 작을 것이고, 그것은 이미 이전에 나누어보았던 값일 것이다.
루트 n보다 큰 약수가 존재한다면, 그 약수로 나눈 몫은 루트 n보다 작을 것이다. 그리고 그것은 이미 나누어 보았던 값일 것이다.
소스코드는 아래와 같다.
Math.sqrt()를 이용해도 된다. i*i를 쓰면 여타 언어에서는 타입이 강타입이라 좋은데, 자바스크립트에서는 사실상 무의미할 수 있다.
let solution = n => {
let originalN = n;
let answer = "";
let i = 2;
while (originalN >= i * i) {
if (n % i === 0) {
n = n / i;
answer += `${i}\n`
continue;
}
i++;
}
if (n > 1) {
answer += `${n}\n`
}
return answer;
}
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();
});