cksgml3808   1년 전

n+1 부터 2*n 까지의 숫자를 vector에 저장하여

vector의 첫번째 요소부터 마지막요소까지 소수인지 확인하고 소수가 아니면 ++count해주어 

전체 vector의 길이에서 소수가 아닌 숫자의 개수를 빼주면 될것이다라고 생각하여 코드를 작성하였습니다.

10% 이후에 시간초과가 뜨는데 어떻게 개선해야될지 여쭤봅니다.

jiminp   1년 전

여러 문제가 있는데, 제일 눈에 띄는건 여러 개의 테스트 케이스에서 이전에 소수 여부를 계산해 놓은 결과를 재사용하지 않고 있다는 것입니다. 123456을 여러 개 주는 테스트 케이스에서 매 번 123456개 숫자의 소수 판정을 계산해야 하죠.

이 이외에도 문제점은 꽤 있습니다. 간략하게 적자면:

  • 각 수에 O(sqrt N)의 소수 판별 검사를 하고 있음 => 에라토스테네스의 체를 이용하면 됩니다.
  • 소수 판별 검사가 비효율적임.
    • 매번 sqrt 함수를 호출하고 있음.
    • k가 2부터 1씩 증가함. k=2를 제외하고 짝수는 검사할 필요 없습니다. 짝수 여부를 체크한 다음에는, k를 3부터 2씩 증가시키면 됩니다.
    • 소수가 아님을 판단했을 때, 그 자리에서 break하지 않고 굳이 sqrt(2*N)까지 전수 검사를 하고 있음.
  • input을 굳이 vector에 저장해 넣고 있고, 처음에 reserve를 하지도 ᅟ않고 굳이 매번 shrink_to_fit을 불러주고 있음. 매번 메모리 할당을 해야 하니, 실행 시간이 줄어들게 됩니다.

cksgml3808   1년 전

  • 매번 sqrt 함수를 호출하고 있음
    • 원문 코드 26줄의 sqrt(2*n)부분을 변수에 할당하여 입력이 주어졌을 때 한번만 수행하게 바꾸었더니 해결되었습니다.
  • 소수 여부를 계산해 놓은 결과를 재사용하지 않고 있다는 것
    • (123465*2) + 1 크기의 vector에 0~123456*2숫자를 넣고 input으로 숫자가 주어졌을 때 해당 vector범위를 소수판별 후 카운트를 해주었더니 해결되었습니다.
    • 이 방법은 쓸데없이 메모리를 크게 잡는다고 생각하여 다른 방법으로도 생각하게 되었습니다.
  • input을 굳이 vector에 저장해 넣고 있음
    • input의 범위를 n+1 ~ 2 * n 까지 설정하여 그 안에서 에라토스테네스의 체 방법을 활용하여 굳이 vector에 저장하지 않고 문제가 해결되었습니다.
    • 굳이 vector공간을 할당하지 않더라도 문제를 해결할 수 있었습니다.

질문과 댓글 작성이 처음이라 답변이 달리지않을까 걱정했었는데 감사할 따름입니다.

공부에 많은 도움이 되었습니다 감사합니다.

댓글을 작성하려면 로그인해야 합니다.