일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 자료구조
- 책추천
- IntelliJ
- 응용SW
- Eclipse
- html
- js
- TSX
- SQL
- Oracle
- set
- script
- deque
- java
- 정처산기
- Algorithms
- 이클립스
- npm
- 수학
- input
- 에라토스테네스의 체
- 백준
- node
- HashMap
- BREW
- googleChart
- 문제풀이
- jsp
- react
- Stack
- Today
- Total
목록에라토스테네스의 체 (2)
개발하자

안녕하세요 :)적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자 글을 써 내려갑니다. 백준 17103 골드바흐 파티션처음엔 단순한 소수 쌍 찾기 문제처럼 보이지만, 입력 수가 많고 범위도 크기때문에시간초과에 걸리지 않도록 효율적인 소수 판별 방법이 꼭 필요합니다. 📘 문제 💡 해결 방법문제에서 짝수 n을 입력으로 주고, 두 소수의 합으로 n을 만들 수 있는 경우의 수를 구하라고 합니다.이때 (3, 7) 과 (7, 3)은 같은 파티션으로 간주하므로 중복을 제거해야 합니다.매 입력마다 소수를 판별하는 방식은 시간초과가 나기 때문에 한 번만 소수 리스트를 전처리하는 방식인에라토스테네스의 체를 사용해야 합니다. 에라토스..
안녕하세요 :)적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자 글을 써 내려갑니다. 오늘은 에라토스테네스의 체 알고리즘에 대해 알아보려고 합니다! 📌 에라토스테네스의 체 (Sieve of Eratosthenes)소수(Prime Number)는 1과 자기 자신 외에는 나누어지지 않는 수를 말합니다.예를 들어 2, 3, 5, 7, 11 등의 소수입니다.에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 고안한 알고리즘으로,2부터 N까지의 모든 소수를 효율적으로 구할 수 있는 방법입니다. 🔍 알고리즘 아이디어1. 2부터 N까지의 숫자 리스트를 만든다2. 리스트에서 2는 소수이므로 남겨두고, 2의 배수들을 모..