[백준] 1644: 소수의 연속합 - JS(투포인터)

목 차 문제 접근 방식 풀이 문제 단, 20은 0인데, 20은 소수가 아니기 때문에 0이 나와야 한다. 접근 방식 2~N까지의 소수를 모두 구해야 하기 때문에 이전에 '소수 구하기'에서 구현했던 코드를 가져와 M부터 N 이였던 것을 처음부터 N 까지로 변경했다. 그리고 이 문제를 읽으면서 두 포인터 기법을 사용해야 겠다고 생각했다. 먼저 소수를 배열에 넣는다. 그리고 start와 end가 있는데 먼저 가장 첫 번째 요소를 가리키게 해 준다. 만약 N과 같거나 작다면 end를 하나 올려준다. start와 end가 1 이상 차이 나게 되면 그 요소들을 더해준다. 그리고 똑같이 N과 같거나 작다면 end를 하나 올려주고, N 보다 크다면 start를 하나 올려주어 결과적으로 맨 앞에 있는 요소를 빼는 역할을 ..

Algorithm 2023.09.30

[백준] 1929: 소수 구하기 - JS (에라토스테네스의 체)

목 차 문제 접근 방식 풀이 문제 접근 방식 에라토스테네스의 체 알고리즘은 큰 범위 내에 있는 모든 소수를 빠르게 찾을 때 효율적이다. 기본 원리는 다음과 같다. - 2부터 원하는 숫자 N 까지의 모든 숫자를 나열한다. - 2는 소수이므로, 2의 배수를 모두 제거한다. - 다음 남아있는 숫자인 3의 배수를 모두 제거한다. - 다음 남아있는 숫자인 5의 배수를 모두 제거한다. - 다음 남아있는 숫자인 7의 배수를 모두 제거한다. - 다음 남아있는 숫자인 ... ... 이런 방식으로 N 까지 한다. 남아 있는 숫자들이 2 부터 N 까지의 소수이다. 그리고 다른 방식은 숫자 N을 2 부터 루트N 까지 나누어 보는 것이다. 이 두 방식의 차이점은 메모리 제한, 시간 복잡도 이다. 에라토스테네스의 체 알고리즘은 ..

Algorithm 2023.09.30