PS와 개발을 공부하자

Modular 연산 줄여서 속도 빠르게하기 본문

Algorithm/Memo &Tips

Modular 연산 줄여서 속도 빠르게하기

sgc109 2017.04.30 22:18

이건 확실한건아니고 들은 사실인데 모듈러를 많이하면 생각보다 속도 저하가 있다고한다. 그래서 코포에서 고수들도

모듈러 연산을 줄이는 테크닉을 많이 쓴다고 들었는데


ans 를 구할 때 어떤 여러개의 답들을 곱해서 모듈러연산을 한거라면 못쓰고..

더해서 구할땐 쓸 수가 있는데 더하는 것들이 둘다 mod 미만이라는 것이 보장되기 때문에

아무리 더해봤자 2*mod 미만일 것이다. 그렇기 때문에

ans %= mod 를 하는대신

while(ans>mod)ans-=mod;


를 하면 while 문이 한번만 돌기 때문에 모듈러를 하는 대신 - 연산을 한번 하게 된다.

근데 이게 꽤 성능 차이가 난다고 하는데 아직 나는 겪어 본적이없다.. 어떤 사람이 2초 제한인 문제에서

모듈러를 그냥 썼을 땐 TLE 가 났는데 저렇게 while 문으로 했을때 0.8 초가 나왔다고 한다.

0 Comments
댓글쓰기 폼