tlawotjd123   3년 전

b보다 작거나 같은 자연수 제곱근들을 for문돌려 while문을통해 그 제곱근들의 배수를 빼주는 과정

즉 에라토스테네스의 체를 활용하여 코드를 짰습니다.

나름 줄인다고 고민많이하고했는데 어느부분에서 줄여야할지 이제 감이안오네요

고수님들 살려주십쇼 

1207koo   3년 전

일단 에라토스테네스의 체는 O(nloglogn)인데, 이 코드는 적어도 O(nsqrt(n))입니다.

에라토스테네스의 체는 소수에 대해서만 배수를 제거하는 식으로 더 줄일 수 있습니다.

그리고 오일러의 체도 있긴 합니다. 굳이 안 써도 될 것 같지만...

추가로 7번째 줄에 value in list가 빠르게 계산될지는 모르겠습니다. 또한 소수에 대해서만 배수를 제거하는 식으로 하려면 boolean list(array)로 표현하는 것이 나을 수 있습니다.

tlawotjd123   3년 전

O(nloglogn)와 O(nsqrt(n)) 뭔지 여쭤봐도될까요 ?-?

jh05013   3년 전

문제는 7줄과 8줄이 각각 한 번 호출할 때마다 O(N)이 걸린다는 것입니다. x in t를 계산하려면 t 전체를 훑어야 하고, t.remove(x)를 하려면 x 이후에 나오는 원소를 전부 한 칸씩 왼쪽으로 옮겨야 하기 때문입니다. 

O()의 뜻에 대해서는 "시간 복잡도"를 공부해 보시는 것을 추천드립니다.

소수일 때에만 배수를 지우는 처리를 하지 않아도 O(NlogN)이기 때문에 통과 가능합니다.

tlawotjd123   3년 전

시간복잡도라는 개념을 알게되어 좋습니다ㅜㅜ 고수님들 감사합니다 꾸벅

시간초과에 어떻게 대응해야알지 조금은 다가간거같습니다

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