blutics   5년 전

knob의 종류/거리에 대한 벡터를 만들고 거리 0대해서 1로 업데이트를 해준다음.

그 벡터를 coefficient로 가지는 polynomial을 만들고 이 폴리노미얼을 가지고 multipy 즉 제곱을 해서

나오는 coefficient들 중에서 첫번째는 0으로 업데이트하고 나머지는 1로 떨어뜨리면 2번에 갈 수 있는 거리들이 나오더라구요.

그리고 hole은 200001크기로 리스트를 만들고 인덱스는 거리를 나타내고

값을 받는 족족 그 인덱스에 대해서 1씩 증가시켰습니다.

그러면 shot과 hole이 각각 나오는데 여기서 shot의 길이만큼

인덱스를 돌면서 각각의 요소들을 곱해서 그 값을 더해가면서

답을 얻었습니다. 

이게 O(nlogn)인거 같은데....음 시간초과가 나오더라구요.

가장 기본적인 fft를 사용했다고 하더라도 어차피 복잡도는 같아서

신경안썼는데....음......잘못된건가요??

jh05013   5년 전

Python3는 정해여도 시간초과가 날 수 있습니다. Pypy3는 아직 완전하지 않고 Pypy2가 좋습니다. 그 때는 파이썬2 문법으로 바꿔야 하긴 한데 여기서는 바꿔야 될 부분이 없는 것 같습니다.

그렇게 바꾸면 3초 정도에 통과되고, 재귀 없이 FFT를 구현하면 2배 빨라집니다.

http://topology-blog.tistory.c...

jh05013   5년 전

그리고 0!=float('%f'%x[i].real)) 이 부분이 꽤 위험해 보입니다. 일단 str 씌우고 다시 float을 씌울 것 없이 그냥 x[i].real이라고만 해도 되는데, 그와 별개로 실수는 오차 문제가 심각하기 때문에 0.0000000001 같은 경우를 못 잡을 수도 있습니다. round 함수로 반올림을 해 보세요.

blutics   5년 전

아닛!!! 감사합니다!!!!

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