jormal   9년 전

팰린드롬을 이미 만든 상태에서 소수를 확인하는게 빠르다는걸 알게되어서 문제를 푸는중에

100%에서 시간초과가 떠버리네요...

체거르기가 시간잡아먹는거같은데 다른 방법 없을까요..

아니면 코드에서 문제가 있나요..?

yukariko   9년 전

특정 수가 소수인지는 O(root(n))으로 가능할탠데 이걸 말씀하시는건가요?

범위로 소수를 판단하는것중에 빠른건 에라토스테네스밖엔 모르겠네요.

yukariko   9년 전

그리고 전역변수로 변수를 선언하면 0으로 자동 초기화되있더라구요.

따라서 memset을 지워보심이..

jormal   9년 전

광역 소수 판단이 필요해서... root(n)으로 해버리면

오히려 느리게될거같아요

jormal   9년 전

아 맞아요 감사합니다. 일단은 제출을 해볼게요...

yukariko   9년 전

저도 그렇게 생각합니다만 제목에 특정 수라고 되있길래 말씀드려봤어요 ㅎㅎ

jormal   9년 전

미ㅏㅜ재ㅑㅜ맙줴ㅐ줓ㅈㄷ무팸ㄷ쟈ㅠ펨

yukariko   9년 전

ㅋㅋㅋㅋㅋㅋㅋ 저도 봤는데 ㅋㅋㅋㅋ

yukariko   9년 전

10000 번밖에 돌지않아서 혹시나 싶긴한데

lgn 함수를 쓰지않고 배열에 미리 저장해서 쓰면 훨씬 빠르지 않나 싶어요

a[1,10,100,1000] 이렇게요

jormal   9년 전

똑같지않을까요?... 그보단 근본적인 문제가있는거같아요.... 좀더찾아보고오겟습니다..

yukariko   9년 전

저 문제는 미리 정답을 다 구해놓고 뿌리는 사람이 꽤 많다죠.. 맞은 사람에 소스 길이를 보면..

pl0892029   9년 전

N의 최대가 1억이지만, 가능한 모양은 최대 $sqrt{N}$개밖에 되지 않습니다.

따라서 가능한 모든 펠린드롬을 만들어두고, 범위 조건을 만족하는 수들만을 모아줍니다. 

이후 각각의 수들에 대하여 소수인지 검사를 하는데, 이 소수 판별법 역시 최대 $sqrt(N)$만큼을 경과하게 됩니다.

따라서 이 둘을 곱하게 되면 O(N)의 시간복잡도로 이 문제를 해결할 수 있습니다.

에라토스테네스의 체는 범위를 거르는 것에는 매우 빠르나, 이 시간복잡도는 O( N lnN + Nψ ) (여기서 ψ는 1 이하의 상수라 생각하시면 됩니다.) 가 걸린다고 알려져있습니다.

따라서 일반적으로 시간복잡도를 O(NlogN)으로 생각하셔도 시간 계산에는 큰 무리가 없습니다. (N은 당연히 범위라는걸 이해하시리라 생각합니다.)

에라토스테네스의 체를 통해 인덱스를 방문하는 횟수를 세서 출력해보시면, 어느정도로 횟수가 걸리나를 예측할 수 있습니다. 가끔은 긴가민가할떄 이걸 직접 출력해서 몇번이나 세는지 보면 좋죠...

jormal   9년 전

하.... 감사합니다... root(n)이 더 빠른거엿네요..

adream   9년 전

아 참고로 저는 너무 오래걸려서

아웃풋 파일 뺸다음에

배열로 옮겼습니다 ㅋㅋㅋ

adream   9년 전

배열로 옮긴거

pl0892029   9년 전

abcddcba 형태의 짝수 형태에서는 소수가 불가능함도 문제에서 강력크한 힌트가 됩니다.

1 * 10000001 * a = 1 * 11 * 909091 * a

10 * 100001 * b = 10  * 11 * 9901 * b

100 * 1001 * c = 10 * 11 * 91 * c

1000 * 11 * d

a와 b, c,d는 모두 11을 소인수로 가지고 있기 때문에 소수가 될 수 없습니다. 따라서 홀수개일때만 검사하면 효율이 무지막지하게 올라가겠네요.

코딩하면 재밌겠는데요? ㅋㅋ

h0ngjun7   9년 전

에라토스테네스 체 알고리즘의 시간복잡도는 O(n log(log n))입니다. n log n보다도 훨씬 빠릅니다.

간단하게, 우선, 1/n + 2/n + ... n/n을 1/x의 연속함수라하고 적분하면 log n이 되는데, 체에 의해 걸러지는 것들은 더해지지 않아서 log(log n)이 됩니다.

루트(n) 알고리즘을 쓰기보다는, n의 범위를 잘 파악하여 에라토스테네스 체 알고리즘을 사용하는 걸 권장드립니다.

예를 들어 x가 소수인지 알아보려면, 루트(x)까지 에라토스테네스 체 알고리즘으로 모든 소수를 구해놓은 뒤, x를 구해놓은 소수들로 다 나눠보다가, 안 나누어진다면 소수라고 판정할 수 있죠.

pl0892029   9년 전

@hongjun7 오... 대박 신기하네요. 에라토스테네스의 체를 그렇게 응용할수도 있군요.

+ 위의 내용 정정합니다. 유일하게 성립하는 짝수 11은 포함시켜줘야되는군요. ㅠㅠ

adream   9년 전

baekjoon   9년 전

@pl0892029

\(\sqrt{n}\) 은 $ 말고 \ (와 \ )로 사용할 수 있습니다. (\와 (사이에 공백없이)

h0ngjun7   9년 전

에라토스테네스의 체 또한 루트(n) 알고리즘을 응용한 알고리즘이 아닙니다.

2의 배수를 다 지우고, 3의 배수를 다 지우고, 5의 배수를 다 지우고, 7의 배수를 다 지우고.... 하는 것과 루트와는 관계가 없죠.

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