백준 1963번 - 소수 경로 (JavaScript)

생각해보기

에라토스테네스의 체

• 대량의 소수를 한꺼번에 판별하고자 할 때 사용
• loose upper-bound : O(NlogN)
• proper upper-bound : O(Nlog(logN))

2이상 N이하인 범위 내 모든 소수를 구할 때, 에라토스테네스의 체를 이용할 수 있다. 이때, 2이상 √N이하인 소수의 배수들을 해당 범위 내에서 제외시키는 방식으로 구할 수 있다. 또한 소수의 배수들을 제외시킬 때, 해당 소수의 제곱부터 시작하면 된다. 이 이유는 아래에서 설명한다.

 

loose upper-bound

2이상 N이하의 모든 자연수에 대해, 소수의 배수들을 제외하는 연산의 횟수를 계산해보자. 먼저 근사화를 통해 해당 범위 내 모든 소수의 배수가 아닌 모든 자연수의 배수를 제외시키는 상황을 가정한다. 예를 들어 2를 제외한 2의 배수를 모두 지우고, 3을 제외한 3의 배수를 모두 지우고, 4를 제외한 4의 배수를 모두 지우는 방식으로 진행한다. 중복되는 연산이 존재하지만 해당 방식 또한 범위 내 모든 소수들을 판별할 수 있다.

 

예를 들어 N = 100이라고 하면, 2의 배수를 지우는 횟수는 약 50번, 3의 배수를 지우는 횟수는 약 33번으로 가정할 수 있다. 즉, N/2 + N/3 + N/4 + N/5 + ... + (N-1)/N + N/N으로 나타낼 수 있다. 이를 N으로 묶으면 N(1/2 + 1/3 + 1/4 + ... + 1/N)으로 표현할 수 있다. 여기서 1/2 + 1/3 + 1/4 + ... + 1/N을 1 + 1/2 + 1/3 + 1/4 + ... + 1/N으로 가정하면 이는 다음과 같이 나타낼 수 있다.

 

1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + ... ≥ 1 + (1/2 + 1/2) + (1/4 + 1/4 + 1/4 + 1/4) + ... = 1 + 2*(1/2) + 4*(1/4) + ...

 

항이 3개일 경우 합은 log(3), 항이 8개일 경우 합은 log(8)이다. 즉 1 + 1/2 + ... + 1/N은 log(N)으로 나타낼 수 있다. 따라서 근사화를 통해 계산한 연산 횟수는 Nlog(N)이다.

 

proper upper-bound

합성수와 합성수의 배수들은 해당 합성수를 나타내는 어떤 소수 인수의 배수이므로 이미 지워졌을 것이다. 예를 들어 4의 경우, 2*2로 나타낼 수 있으므로 2라는 소수에 의해 지워졌을 것이다. 또한, 7의 배수를 지울 때 7*7, 7*8, ...의 방식으로 진행한다. 7*2, 7*3, 7*4, ... 7*6의 경우 이미 이전 소수들에 의해 제외되었기 때문이다. 이를 고려하면 합성수 차례를 띄어넘을 수 있고, 소수의 경우에도 해당 소수의 제곱부터 지우는 연산을 시작할 수 있다. 이렇게 할 경우, 시간복잡도는 O(Nlog(logN))이다.

 

임의의 수 N에 대한 소수 판별

• N에 대해 2이상 N의 제곱근 이하의 수로 나머지 연산 수행
• O(n^(1/2))

---

• BFS를 통한 소수 탐색
• 숫자를 문자열로 변환하여 연산 수행 → 인덱스와 연관지어 로직 작성하기
• cnt += 1로 작성 시, 같은 변환 횟수에 대해 변환 횟수가 누적되어 큐에 삽입되므로, queue.push()의 인수로 cnt + 1로 작성해야 한다.

 

풀이)

const readline = require("readline");

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

const solution = (num, data) => {
  let prime = Array.from({ length: MAX }, () => true);
  let visited = Array.from({ length: MAX }, () => 0);

  // 에라토스테네스의 체
  for (let j = 2; j <= Math.sqrt(MAX); j++) {
    // 소수가 아니므로 continue
    if (prime[j] == false) continue;
    // i * k (k < i)까지의 수는 이미 검사했으므로 j는 i * i부터 검사
    for (let k = j * j; k < MAX; k += j) {
      prime[k] = false;
    }
  }

  let start = data[num][0];
  let end = data[num][1];

  visited[start] = 1;
  let queue = [[start, 0]];

  while (queue.length) {
    let [now, cnt] = queue.shift();
    strNow = String(now);
    if (now == end) {
      return cnt;
    }
    for (let p = 0; p < 4; p++) {
      for (let q = 0; q < 10; q++) {
        let temp = parseInt(strNow.slice(0, p) + q + strNow.slice(p + 1, 4));
        if (visited[temp] == 0 && prime[temp] && temp >= 1000) {
          visited[temp] = 1;
          // 같은 변환 횟수로 큐에 들어가야 함
          queue.push([temp, cnt + 1]);
        }
      }
    }
  }
  return "impossible";
};

let T = null;
let MAX = 10000;
let data = [];
let count = 0;

rl.on("line", function (line) {
  if (!T) {
    T = parseInt(line);
  } else {
    data.push(line.split(" ").map(Number));
    count += 1;
  }
  if (count == T) {
    rl.close();
  }
}).on("close", function () {
  for (let num = 0; num < T; num++) {
    console.log(solution(num, data));
  }
  process.exit();
});

 

참고자료

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity

Sieve of Eratosthenes - Wikipedia

 

https://en.wikipedia.org/wiki/Harmonic_number

Harmonic number - Wikipedia

 

https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes

Divergence of the sum of the reciprocals of the primes - Wikipedia