john6014   10달 전

10859 문제 [ 숫자 뒤집기 인가?] 저 문제를 풀긴했는데요 어우. 다른 분들 보니까 0ms 있고 무쟈게 짧더라구요

근데 언어를 보니까 거의다 C++11 인가 이거던데 언어차이면에서도 걸리는 시간이 조금 다를까요?

각 언어에서 제공해주는 형식 및 라이브러리가 다르긴한데..

isac322   10달 전

일단 c랑 python같이 컴파일 언어 vs 인터프리트 언어라면 당연히 언어에서 차이가있겠죠?

그걸 제외한다면 언어마다, 컴파일러마다 라이브러리의 구현이 얼마나 최적화 되었냐 일탠데, 우리가 알만한 언어는 이미 유명한 언어기에 라이브러리끼리의 성능 차이는 비등비등하겠죠.

나머지는 전부 프로그래머의 해당 언어 습득력과 알고리즘선택, 최적화가 시간차이를 결정해요.

10859같은 문제도 보면 큰 수의 소수 여부판단을 빠르게하는게 관건인데, 소수판단 알고리즘들 이 중 어떤 알고리즘을 선택해서 구현했느냐가 시간차를 가르는것 같네요.

joonas   10달 전

언어보다는 알고리즘의 차이가 더 큽니다.
근데 소수판별 중에 Miller-Rabin 라고 있던데, 이거 확률적인건가요?! $ 10^{12} $ 쯤 되니까 판별이 안되네요 ㅠㅠ

john6014   10달 전

아직 모르겠어요 ㅎ 소수 판별 알고리즘이 너무 많아서 어떤게 가장 좋은 알고리즘인지도 모르겟고..

저도 하나씩 공부하면서 그냥 최근에 공부한 소수판별알고리즘으로 짠건데.. 나름 빠른 알고리즘을  선택했다고햇는데도 저거 보다 훨씬좋은 알고리즘이 존재하네요 ㅋㅋ

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