https://www.acmicpc.net/p roblem/902090~20회 제출 받은 사람 쇼트 코딩 재채점 결과 △ 채점 현황 강의 골드 바흐 추측, △ 출처, △는 다국어 시간 제한, △ 메모리 제한 제출 △ 정답된 사람의 정답율 △ 2초 256MB38893165311284~41.654%, △ 문제 1보다 큰 자연수 가운데 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라는. 예를 들어 5는 1과 5를 제외한 약수가 없어 소수이다.
하지만 6은 6=2×3에 소수가 없다.
골드 바흐 추측은 유명한 정수론의 미해결 문제로, 2보다 크게 모든 짝수는 두 소수의 합으로 나타내…www.acmicpc.net내가 잘못된 첫번째 방법 소수에 키우기 1.g=n부분이 문제이다.
만약 g이 짝수의 경우에는 소수를 구할 때, 잘못된 방식으로 요구하게 될 뿐 아니라, 위의 코드에서는 반복적으로 list를 계속 추가하는 방향이다.
즉, 위의 코드는 중복되는 양상으로 발생하므로, 시간의 복잡도가 그다지 줄어들지 않을 뿐 아니라, 애초에 소수를 구할 때 매우 잘못된 방식이다.
Tip 소수를 파악하는 문제의 경우에는 우선 전체 소수의 개수를 파악한 후 출력 시 사용하는 것이 효율적이다.
세트를 만드는 경우에 주의하는 2. 세트(리스트)는 리스트의 길이만큼 시간을 필요로 한다.
즉, 세트에서의 시간 복잡도는 O(1)이지만, O(N)만큼 사용하게 된다.
O(O(N))가 되는 것이다.
The time complexity of converting a list to a set is linear in the number of list elements . So , if the set has n elements , the asymptotic complexity is O ( n ) . The reason is that you need to iterate over each element in the list which is O ( n ) , and add this element to the set which is O ( 1 ) .
해석하여 요약하면 세트가 리스트를 세트로 바꿀 때 과정에서 리스트를 파악해야 하기 때문에 시간이 걸린다.
도와주신 분 – 감사합니다!
!
요약하면 1.세트 안에 목록을 넣어 사용하지 않고 따로 만들어 하나의 변수로 사용한다 2.소수를 구하는 문제에서는 구하지 말고 미리 전체를 먼저 파악한 뒤 구하는 것이 효율적이다.
3. 항상 범위부터 우선적으로 파악하고 작성한다(범위주의!
!
)