에라토스테네스의 체2 [Java] 백준 1644번 소수의 연속합 952hi의 접근방법 1. 문제접근 1)2이상 N이하 소수를 구해야 합을 구할 수 있겠다. 소수를 구하려면 에라토스테네스의 체를 사용해야겠다고 생각이 바로 들었다. 에라토스테네스의 체를 간단하게 설명하자면 2부터 N의 제곱근까지 범위에서 체크하지않은 수가 들어오면 소수로 판단하고 소수의 배수 전부를 체크배열에서 체크해 다음 소수판단에서 삭제하는 알고리즘이다 시간복잡도가 O(N/2)으로 굉장히 빠르다. 2)구한 소수를 연속으로 합쳐 주어진 N을 만들 수 있는지 판단해야겠다. 구한 소수 체크배열을 통해 체크안된 값은 소수이므로 리스트로 구현해 N이 굉장히 클때 탐색시간을 줄여야겠다고 생각했고 슬라이딩윈도우방식으로 매번 소수의 합을 구하고 N보다 작으면 윈도우 크기를 크게만들고 N보다 커지면 중지시켰다. 2. 느낀점 처음에 목표값.. 2022. 6. 13. [JAVA] 백준 1929 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 클래스2++도전기 나만의 문제접근방법 1. 소수는 약수가 1과 그수 자신인 숫자라고 알고 있었다. 2. 시작이 3 끝이 16이면 3부터 반복문을통해 일차원적으로 소수인지 아닌지 검토하는 방식 -> 시간초과 메모리간당간당 3. 뭔가 알고리즘이 있을것같아 찾아보니 에라토스테네스의 체라는 알고리즘을 사용하거나 더 뛰어난 알고리즘을 사용해야했었다. 4. 간단히 공부 후 코드를 작성해 제출했음 어려웠던 점 출력해줄때 0,1을 예외처리해주.. 2022. 3. 28. 이전 1 다음
