일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 프로그래머스
- 문자열
- 플로이드-와샬
- 그리디
- 투 포인터
- 에라토스테네스의 체
- 완전탐색
- 구현
- 수학
- 백준
- JUnit 5
- dfs
- 유니온 파인드
- Effective Java
- CS
- Kotlin
- 백트래킹
- 위상정렬
- java
- swea
- 시뮬레이션
- 동적계획법
- 스택
- 후니의 쉽게 쓴 시스코 네트워킹
- mst
- 알고리즘
- BFS
- 이분탐색
- Network
- 세그먼트 트리
목록에라토스테네스의 체 (5)
반갑습니다!
1644번: 소수의 연속합 boj.kr 풀이 소수를 찾아 배열에 모두 저장한 뒤, 투 포인터 알고리즘으로 해결하면 된다. 아래의 코드에서는 에라토스테네스의 체를 사용해 소수를 판별했다. 코드 C++ Python3
2153번: 소수 단어 boj.kr 풀이 에라토스테네스의 체를 사용해 1부터 최대값인 20 * 52 까지의 범위에 있는 소수를 모두 구한 뒤, 입력 들어온 문자열을 숫자로 바꿔서 소수 여부를 확인했다. 코드 C++ #include using namespace std; const int MAX = 20 * 52; int main() { bool arr[MAX + 1]; for (int i = 1; i
6588번: 골드바흐의 추측 www.acmicpc.net 풀이 에라토스테네스의 체를 사용해서 소수를 모두 구한 뒤, 3부터 시작해서 수를 탐색하기 시작한다. 가장 작은 홀수 소수인 3부터 홀수만 탐색하므로 처음으로 발견되는 두 수의 차이가 가장 크다는 것을 보장할 수 있다. 코드 #include #include using namespace std; bool chk[1000001]; void precalc() { fill(chk, chk + 1000001, true); chk[1] = false; for (int i = 1; i * i n; if (n == 0) break; bool find = false; // 3부터 시작해서 홀수만 탐색 for (int i = 3; i < n; i += 2) { // ..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 에라토스테네스의 체를 이용해서 소수를 미리 계산해두고 DFS를 사용하여 숫자 3개를 골라 해결하였다. 코드 #include #include using namespace std; int ans; bool chk[3001]; void precalc() { fill(chk, chk + 3001, true); chk[0] = false; chk[1] = false; for (int i = 2; i * i
소수 찾기 문제를 풀고 기왕 포스트하는김에 이론정리를 해놓는게 낫겠다는 생각이 들어서 정리하였다. 소수를 찾는 알고리즘이다. 위의 동영상처럼 1부터 N까지 숫자를 순회하며 순회한 수들의 배수를 제거하는 방법이다. 구체적인 구현 방법은 코드를 살펴보자 n을 입력받아서 1~n까지의 숫자 중에서 소수인 숫자를 출력하는 코드이다. #include #include using namespace std; void precalc(vector& prime, int n){ prime[1] = false; for(int i=2; i*i n; vector prime(n+1, true); precalc(prime, n); for(int i=1; i