azaka9541   3년 전

1000000 까지 정확하게 맞추는 걸로 봐서 정확하게 구현한 것 같음.

소수 찾기에서 이 문제로 고생하고 있다면, 아마 소수를 구하는데 1000000까지 주었다고 덥석 에라토스 테네스체 알고리즘 구현해서 

for문 돌아가다 시간초과 나서 고민하는 백수들일꺼임.

확실히 테이블 만들어 놓고 구하는게 빠르긴 한데, 그 테이블을 빠르게 구할 방법은 여러번 for 문 돌면서 소수인지 쳐내는게 아니라

한번에 돌아야함.

아래의 소스는 filter 한방으로 1000000까지 소수 테이블을 구할 수 있음



hjroh0315   3년 전

글이 다소 말이 험해지는 거 같아서 설명 하나만 드립니다.

에라토스테네스의 체는 매 쿼리마다 전체를 한 번씩 계산하라고 있는 알고리즘이 아니고, 전체적으로 한 번 계산한 뒤에 여러 번 재사용하는 알고리즘입니다. 다만, 소수의 개수는 $O(n)$보다 작은 $O(\frac{n}{\log n})$이기에, 이 문제를 해결하는 시간 복잡도의 주요한 차이는 이 부분에서 크게 발생합니다.

에라토스테네스의 체의 시간복잡도는 $O(n \log \log n)$입니다. 일반적으로 $n=10^7$이 되더라도 100~200ms 내에 잘 돌아가는 알고리즘이 에라토스테네스의 체입니다. $n=10^6$인 경우에 에라토스테네스의 체를 사용했다고 시간 초과가 발생하는 일은 코드를 작정하고 구데기같이 짜지 않는 이상 웬만하면 일어나지 않습니다.

azaka9541   3년 전

@hjroh0315 님 이문제 안풀었네?

hjroh0315   3년 전

@azaka9541 5분만에 풀고옴 딱대셈

hjroh0315   3년 전

풀고 왔습니다.

남이야 어떻게 하든 신경 끄고 그냥 하시면 참 좋을 것 같다는 조언 드립니다. "누가 비효율적으로 푸는 거 같아서 불편하다" 그러면 더 나은 풀이를 직접 찾아서 show and prove하시면 됩니다. 계속 더 나은 풀이를 찾아서 노력하는 것이 게시판 글로 보이니 어떻게든 되겠죠.

ash9river   3년 전

시간 제한이 0.5, 5*10^7 개의 연산 횟수가 근사한다 치면, 에라토스테네스10^6loglong10^6+ 골든바흐로 100*10^6/2면 얼추 비슷하게 되네요. 상기 말하신거랑은 다르게 무식하게 에라토스테네스를 써도 될거같네요.

shiftpsh   3년 전

남을 폄하하지 맙시다.

zenith82114   3년 전

밀러라빈을 알고 있더라도 범위가 100만밖에 안 되면 에라체를 짜는 게 진짜 고수의 반응입니다. 아무 문제에나 어려운 알고리즘을 들이대는 게 실력이 아니에요. 글 봐서는 본인도 에라체의 이해가 완전하지는 못한 거 같은데 시간초과 받는 사람들 얕잡을 수 있는 형편이 되실지 모르겠네요.

azaka9541   3년 전

@hjroh0315 ㅇㅋ ㅇㅈ. 남은 호의로 올려논 글에 백수 한마디에 달려나온 사람들 많네.

readiz   3년 전

닭잡는데 소잡는 칼을 쓰시는 분이군요

그렇다고 소잡는 칼을 잘 쓰는 것도 아닌..

공개된 게시판에서는 기본 매너를 지킵시다.

startlink   3년 전

게시판에서는 상대방을 존중해주세요. 그리고 존댓말을 사용해주세요.

hyjin1117   3년 전

오 개간지난다

'랑데부'


근데 스펠링 틀림 수정좀

k550706   3년 전

작성자님 코드 몇개 열어보니 for문 돌리다가 시간초과 내신건 본인이시네요.

이 문제는 pypy3 기준으로 에라스토테네스의 체로 돌리면 300ms 정도에 AC를 받을수 있습니다.

nflight11   3년 전

어제 밤~새벽 즈음에 이 글을 처음 봤습니다. 보자마자 생각나는 대로 덧글을 달면 그렇게 예쁜 소리가 나가지 않을 것 같아서 한 숨 자고 조금 말끔해진 머리로 덧글을 남깁니다.

이미 hjroh0315님 외 수많은 분들이 지적하신 대로 이 문제는 에라토스테네스의 체를 이용하더라도 충분히 빠르게 통과할 수 있습니다. 이게 맞는 것 같은데 자꾸 시간초과가 나서 다른 알고리즘을 가지고 오신 것 같은데, 아쉽게도 밀러-라빈 소수판정법은 매우 빠르기는 하나 이 문제에는 그렇게 어울리지 않는 알고리즘입니다. N 이하의 모든 소수를 구해 놓고 for문을 돌리는 돌리는 방식으로 문제를 풀어야 하는데, 밀러-라빈은 한 번에 하나의 수만 소수 판정을 수행할 수 있기 때문입니다.

오히려 1e6 이하의 모든 N에 대해 판정한다면 에라토스테네스의 체는 NloglogN, 밀러-라빈은 Nklog³N의 시간이 소모되어 밀러-라빈은 경우에 따라 더 느릴 수도 있습니다.

언제나 오버킬이 바른 방법은 아닙니다(맞는 방법이긴 하지만요). 혹여 밀러-라빈을 통해 AC를 받았다 하더라도, 과거의 자신이 왜 시간초과가 났는지 다른 정답자들의 코드와 본인의 코드를 비교하여 체크해 보는 것을 추천드립니다.

※ 정말 밀러-라빈을 사용하는 문제를 풀기 원하신다면, solved.ac에서 해당 태그를 가진 문제들을 위주로 검색할 수도 있습니다. 우선 5615번에 도전해 보시는 건 어떨까요?

ksoosung77   3년 전

코드를 잘 짜는것도 중요하지만 사용자의 품위를 지키는것도 중요합니다.

호의 특(남을 백수로 만들어버림)

albert3289   3년 전

말투가 참,,,

twoeg   1년 전

꺼드럭계 GOAT네 ㅋㅋㅋㅋㅋ

azaka9541   1년 전

와씨 백수 어그로가 2025년까 끌리네. 이정도면 인간 쟁기라고 불러다오.

zenith82114   1년 전

좋으시겠어요.

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