백준 1929 소수구하기
기존의 방법은 시간복잡도가 O(N²)가 되어 시간 내에 문제를 풀 수 없다.
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
input = input[0].split(' ').map(item => +item);
solution(input);
function solution(input) {
for (let i = input[0]; i <= input[1]; i++) {
solution2(i);
}
function solution2(num) {
if (num === 1) return;
for (let i = 2; i < num - 1; i++) {
if (!(num % i)) return;
}
console.log(num);
return;
}
}
다음 블로그들을 참고하여 두가지 방법으로 문제를 풀 수 있었다.
1. 제곱근까지만 확인하기
2. 에라토스테네스의 체 이용하기
백준 1929번 소수 구하기 - node.js | 사이다 데브로그 CIDER DEVLOG
[백준 / 1929 / nodejs] 소수구하기 javascript
알고리즘이란?
✳️ 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미
(한 개의 문제도 엄청나게 많은 알고리즘으로 해결 가능하다.)
시간복잡도를 분석 하는 것은 input n 에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것 과 같다.
➡️ 그리고 이는 Big-O 표기 를 이용하여 정의할 수 있다.
Big-O 표기란?
✳️ 시간복잡도에서 중요한 것은 정해진 표현식에 가장 큰 영향을 미치는 n 의 단위
- 1️⃣ O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.
- 2️⃣ O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
- 3️⃣ O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다.
- 4️⃣ O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다.
- 5️⃣ O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱이다.
위의 정의로 계산한 시간복잡도 예시
var n = 16; -- 입력값 n 이 16일 때
O (1) = 1 step "(awesome!)" -- O(1)는 시간복잡도가 1입니다.
O (log n) = 4 steps "(awesome!)" -- O(log n)는 시간복잡도가 4입니다. (log 의 밑이 2라고 가정)
O (n) = 16 steps "(pretty good!)" -- O(n)는 시간복잡도가 16
O(n^2) = 256 steps "(uhh..we can work with this?)" -- O(n^2)는 시간복잡도가 256
O(2^n) = 65,536 steps "(...)"
start!