강의로 돌아가기
dosthcpp

최적화 방법을 잘 모르겠습니다

벡터 다 없애고 코드도 최대한 간단하게 짰는데 효율성 테스트 통과가 안되네요 ㅠㅠ

작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
long long solution(int N) {
    long long answer=0;
    int i, j;

    for(i=2;i<=N;++i){
        for(j=2;j<i && !(i%j==0);++j);
        if(j>=i) answer+=j;
    }
    return answer;
}
1 개의 답변
김용우

효율성 테스트는 코드보다는 로직상 연산이 적어야 합니다. 질문 주신 분의 코드를 살펴보면,

  1. i를 iteration하면서 1씩 증가하는데, 사실 짝수는 2를 제외하고는 살펴 볼 필요도 없이 합성수이기 때문에 불필요한 iteration입니다.
  2. j 또한 1씩 증가하면서 i와 나누어 떨어지는지 반복을 하는데, 이 역시 j가 짝수일 경우는 고려하지 않아도 됩니다. 2를 제외한 소수는 무조건 홀수일 테니까요.
  3. j < i 역시 불필요한 iteration이 포함되었는데, 실제 소수임을 판정하는 반복은 루트 i까지만 해도 충분합니다.
  4. 어떤 합성수는 소수들의 곱으로 이루어져 있기 때문에, 소수 검사는 그보다 작은 소수들로만 나누어봐도 충분합니다.

이를 종합하였을 때, 불필요한 iteration이 많이 보입니다. 이 점 참고하셔서 최적화 방법을 고민해보시면 좋을 듯 싶습니다. :)

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.