자바스크립트로 알고리즘 정리하기 #8 수학3 연습문제

jakeseo_me·2020년 9월 3일
0

javascript-algorithm

목록 보기
8/11

자바스크립트로 알고리즘 정리하기 #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의 형태로 표현이 가능할 것이다. Nab의 곱으로 표현 가능할 때, ab의 차이가 가장 최소가 될 때는 루트 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();
});
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.

0개의 댓글