백준 - 알고리즘 기초 1/2 ( 301 - 수학 1 (연습) )

백준 알고리즘 기초 강의에 명시된 문제를 풀이한 포스트입니다

1. 9613번 - GCD 합

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

const input = [];

rl.on("line", (line) => {
  input.push(line);

  if (+input[0] === input.length - 1) rl.close();
}).on("close", () => {
  // 유클리드 알고리즘
  const getGCD = (x, y) => {
    const bigger = Math.max(x, y);
    const smaller = Math.min(x, y);

    const remainder = bigger % smaller;

    if (remainder === 0) return smaller;
    else return getGCD(smaller, remainder);
  };

  // 전체 입력 개수 분리
  const [count, ...list] = input;
  // 입력 개수만큼 배열 생성
  const answer = Array(+count).fill(0);

  list.forEach((value, index) => {
    // 세부 입력 개수 분리 및 숫자로 변환 후 배열화
    const [, ...numbers] = value.split(" ").map((n) => +n);

    // 모든 경우를 포함해서 최대공약수(GCD) 계산 후 합치기
    numbers.forEach((v, i, arr) => {
      for (let j = i + 1; j < arr.length; j++) {
        answer[index] += getGCD(v, arr[j]);
      }
    });
  });

  console.log(answer.join("\n"));

  process.exit();
});

2. 17087번 - 숨바꼭질 6

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

const input = [];

rl.on("line", (line) => {
  input.push(line);

  if (2 === input.length) rl.close();
}).on("close", () => {
  /**
   * 핵심은 한번에 "D만큼만 이동이 가능"이다.
   * 몇번이든 상관없이 D만큼 이동해서 동생과 같은 위치에 도달할 수 있으면 된다.
   * 즉, "|수빈위치 - 동생위치|"인 값들을 D로 나눠서 나누어 떨어지는 최댓값인 최대공약수를 구하는 문제이다.
   */

  // 유클리드 알고리즘
  const getGCD = (x, y) => {
    const bigger = Math.max(x, y);
    const smaller = Math.min(x, y);

    const remainder = bigger % smaller;

    if (remainder === 0) return smaller;
    else return getGCD(smaller, remainder);
  };

  // 수빈 위치 구하기
  const [, subinLocation] = input[0].split(" ").map((v) => +v);
  // 수빈과 동생들의 거리 계산
  const locations = input[1]
    .split(" ")
    .map((v) => Math.abs(+v - subinLocation));

  // 수빈과 동생들의 거리의 최대공약수 구하기
  const distance = locations.reduce((p, c) => getGCD(p, c));

  console.log(distance);

  process.exit();
});

3. 1373번 - 2진수 8진수

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

let input = "";

rl.on("line", (line) => {
  input = line;

  rl.close();
}).on("close", () => {
  /**
   * 2진수 -> 10진수 -> 8진수 => 시간초과
   * 2진수를 뒤에서부터 3개씩 끊어서 8진수로 변환 후 붙이면 됨
   */

  const binary = input.split("");
  const answer = [];

  // 문자열을 뒤에서부터 3개씩 끊어서 2진수로 만들고 8진수로 변환하는 과정을 계속 반복
  while (binary.length >= 3) {
    answer.push(
      parseInt(binary.splice(binary.length - 3).join(""), 2).toString(8)
    );
  }

  if (binary.length) answer.push(parseInt(binary.join(""), 2).toString(8));

  console.log(answer.reverse().join(""));

  process.exit();
});

4. 1212번 - 8진수 2진수

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

let input = "";

rl.on("line", (line) => {
  input = line;

  rl.close();
}).on("close", () => {
  /**
   * 8진수를 한자리씩 끊어서 2진수로 변환 후 합쳐줌
   * 단, 마지막을 제외하고 3자리가 아닐경우 빈칸에 0을 채워줌
   */
  const numbers = input.split("").map((v) => +v);

  const answer = numbers.map((v, i) => {
    let binary = v.toString(2);

    if (i !== 0) binary = "0".repeat(3 - binary.length) + binary;

    return binary;
  });

  console.log(answer.join(""));

  process.exit();
});

5. 2089번 - -2진수

문제 풀이 실패

6. 17103번 - 골드바흐 파티션

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

const input = [];

rl.on("line", (line) => {
  input.push(line);

  if (+input[0] === input.length - 1) rl.close();
}).on("close", () => {
  // 에라토스테네스의 체로 범위 내 소수 구하기
  const getPrimeNumbers = (range) => {
    const candidates = Array(range + 1).fill(true);
    let loopIndex = 1;

    candidates.forEach((v, index, arr) => {
      // 0은 제외, 1은 예외
      if (index === 1 || index === 0) {
        arr[index] = false;
        return;
      }

      loopIndex = 1;
      for (let i = index; i < arr.length; i = loopIndex++ * index) {
        // 본인은 소수에서 제외
        if (i === index) continue;
        // 이미 소수인 것도 제외
        if (arr[i] === false) continue;

        arr[i] = false;
      }
    });

    return candidates;
  };

  // 홀수 제외 숫자 배열로 변환
  const [, ...numbers] = input.map((v) => +v);

  // 특정 범위 소수 구하기
  const primeNumbers = getPrimeNumbers(Math.max(...numbers));

  const answers = numbers.map((v) => {
    let count = 0;

    for (let i = 2; i <= v / 2; i++) {
      if (primeNumbers[i] && primeNumbers[v - i]) {
        count++;
      }
    }

    return count;
  });

  console.log(answers.join("\n"));

  process.exit();
});