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

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

1. 10430번 - 나머지

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

let input = null;

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

  rl.close();
}).on("close", () => {
  const [A, B, C] = input.split(" ").map((v) => +v);

  console.log((A + B) % C);
  console.log(((A % C) + (B % C)) % C);
  console.log((A * B) % C);
  console.log(((A % C) * (B % C)) % C);

  process.exit();
});

2. 2609번 - 최대공약수와 최소공배수

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

let input = null;

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

  rl.close();
}).on("close", () => {
  /**
   * 유클리드 알고리즘
   * A(큰 수), B(작은 수), q(몫), b(나머지)
   * A % B = B * q + b 일 때 b === 0 일 경우 q가 최대공약수이다. ( 나머지가 0일때 까지 반복 )
   *
   * 최소공배수 === A * B / 최대공약수
   */
  const [A, B] = input.split(" ").map((v) => +v);
  let x = A > B ? A : B;
  let y = A > B ? B : A;
  let q = Math.floor(x / y);
  let b = x % y;
  let GCD = null; // 최대공약수
  let LCM = null; // 최소공배수

  while (b !== 0) {
    x = y;
    y = b;
    q = Math.floor(x / y);
    b = x % y;
  }
  LCM = y;
  GCD = (A * B) / LCM;

  console.log(LCM);
  console.log(GCD);

  process.exit();
});

3. 1978번 - 소수 찾기

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

let input = [];

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

  if (input.length === 2) rl.close();
}).on("close", () => {
  /**
   * 에라토스테네스의 체
   * 2부터 특정 범위까지 순회하면서 해당 수의 배수를 제외한다.
   * 그러면 남은 수는 소수가 된다.
   */
  const getPrimeNumber = (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[1].split(" ").map((v) => +v);
  const primeNumberList = getPrimeNumber(Math.max(...numbers));
  let answer = numbers.filter((v) => primeNumberList[v]).length;

  console.log(answer);

  process.exit();
});

4. 1929번 - 소수 구하기

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

let input = [];

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

  rl.close();
}).on("close", () => {
  /**
   * 에라토스테네스의 체
   * 2부터 특정 범위까지 순회하면서 해당 수의 배수를 제외한다.
   * 그러면 남은 수는 소수가 된다.
   */
  const getPrimeNumber = (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 [min, max] = input[0].split(" ").map((v) => +v);
  const primeNumberList = getPrimeNumber(max);
  const answer = [];

  for (let i = min; i <= max; i++) {
    if (!primeNumberList[i]) continue;

    answer.push(i);
  }

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

  process.exit();
});

5. 6588번 - 골드바흐의 추측

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

let input = [];

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

  if (input[input.length - 1] === "0") {
    input.pop();
    rl.close();
  }
}).on("close", () => {
  /**
   * 에라토스테네스의 체
   * 2부터 특정 범위까지 순회하면서 해당 수의 배수를 제외한다.
   * 그러면 남은 수는 소수가 된다.
   */
  const getPrimeNumber = (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 primeNumebrList = getPrimeNumber(Math.max(...numbers));
  const answer = [];

  numbers.forEach((v) => {
    for (let i = 3; i <= Math.floor(v / 2); i++) {
      // 현재 값이 소수가 아니라면
      if (!primeNumebrList[i]) continue;
      // "현재값 - 특정 소수 === 소수"라면 조건에 만족함  ex) 42 = 5 + 37
      // 또한 제일 작은 소수부터 순회하므로 "b-a"가 제일 큰 것을 출력하는 것을 고려할 필요가 없이 자동으로 검증됨
      if (primeNumebrList[v - i]) {
        answer.push(i, v - i);
        break;
      }
    }

    // 두 개의 소수의 합으로 나태낼 수 있다면
    if (answer.length) {
      console.log(`${answer[0] + answer[1]} = ${answer[0]} + ${answer[1]}`);
    }
    // 나타낼 수 없다면
    else {
      console.log("Goldbach's conjecture is wrong.");
    }

    answer.length = 0;
  });

  process.exit();
});

6. 10872번 - 팩토리얼

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

const input = [];

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

  rl.close();
}).on("close", () => {
  const disit = +input[0];

  // 재귀함수 사용
  const getFactorial = (number) => {
    if (number === 0) return 1;
    if (number === 1) return number;
    return getFactorial(number - 1) * number;
  };

  console.log(getFactorial(disit));

  process.exit();
});

7. 1676번 - 팩토리얼 0의 개수

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

const input = [];

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

  rl.close();
}).on("close", () => {
  /**
   * 마지막에 0이 붙으려면 결국 "2 * 5"의 개수를 세면 된다.
   * 주의할 점은 "15 => 3 * 5" 이므로 5의 개수를 카운팅해줘야 한다는 점이다.
   * 또한 모든 짝수는 2를 포함하므로 팩토리얼에서는 2의 개수는 항상 5보다 많으므로 고려할 필요 없다.
   * 결론: 주어진 숫자의 팩토리얼에서 "*5"가 몆 개 나오는지 카운팅하면 된다.
   */

  // 5가 몆 개 나오는지 세는 함수
  const divideFive = (number) => {
    let count = 0;
    const quotient = number / 5; // 몫
    const remainder = number % 5; // 나머지

    // 5의 배수라면
    if (remainder === 0) {
      count++;

      // 몫이 5의 배수라면 ( 5를 여러 개 포함하는 값임 ex) 25, 125 등 )
      if (quotient % 5 === 0) return count + divideFive(quotient);
    }

    return count;
  };
  const disit = +input[0];

  let answer = 0;

  for (let i = 5; i <= disit; i += 5) {
    answer += divideFive(i);
  }

  console.log(answer);

  process.exit();
});

8. 2004번 - 조합 0의 개수

이 문제에서 의문은 팩토리얼의 조합이라고 해도 어떻게 2의 개수가 5보다 작은 경우가 있는지 모르겠음

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", () => {
  /**
   * 조합 공식 "nCm === n!/m!(n-m)!"
   * 즉, n!의 0의 개수 - m!의 0의 개수 - (n-m)!의 0의 개수
   */

  // 5가 몆 개 나오는지 세는 함수
  // 125!을 예를 들면 5는 "125/5"만큼 가지고, 5*5는 "125/(5*5)"만큼 가지고, 5*5*5는 "125/(5*5*5)"만큼 가짐
  // 해당 규칙을 코드로 표현하면 아래와 같음
  const countFive = (number) => {
    let count = 0;

    for (let i = 5; i <= number; i *= 5) {
      count += Math.floor(number / i);
    }

    return count;
  };
  // 2가 몇 개 나오는지 세는 함수
  const countTwo = (number) => {
    let count = 0;

    for (let i = 2; i <= number; i *= 2) {
      count += Math.floor(number / i);
    }

    return count;
  };

  const answer = [];
  const [n, m] = input.split(" ").map((v) => +v);

  // >>> 팩토리얼에서 어떻게 5가 2보다 적게 나오는 경우가 있는지 이해가 안감
  answer.push(countFive(n) - countFive(m) - countFive(n - m));
  answer.push(countTwo(n) - countTwo(m) - countTwo(n - m));

  console.log(Math.min(...answer));

  process.exit();
});