redpigeon   4년 전

굳이 이 문제에만 국한된 질문은 아닙니다.

최근에 어려운 문제들을 찾다가 들어오게 된 문제들을 풀어봤는데요

제가 요즘에 파이썬을 공부중이라, 이미 제출해서 통과한 C++, JAVA코드를 파이썬으로 작성해서 제출해 봤습니다.

근데.. 이미 통과했던 코드가, 파이썬으로 제출하면 Subtask 1만 통과하거나, 아예 시간 초과가 떠버리더군요.

동일한 알고리즘이면, 당연히 동일한 시간 복잡도를 가질테고.. 그렇다면 결국 언어별 수행 시간이 이렇게나 유의미하게 차이가 난다는 것일까요?

채점 기준을 찾아보니, 파이썬의 경우, C/C++ 제한시간의 x3+2초라고 되어 있던데..

(https://www.acmicpc.net/help/language)

흠.. 동일한 알고리즘에서도 언어별로 시간 초과가 발생한다면, 시간 기준이 좀 개선되어야 하지 않을까요?

아니면 이 문제의 경우 보너스 시간이 없던 것인지...

흠.. 고민이 많습니다ㅠㅠ

최근에 파이썬을 배우기 시작하면서 참 좋은언어다 싶었는데

이렇게 유의미한 차이가 발생해버리면.. 현업에서 쓰기가 좀 어렵지 않을까 싶어서요ㅠㅠㅠㅠ


redpigeon   4년 전

흠.. PyPy도 시도해봤지만, 여전히 실패네요..

동일한 알고리즘으로 작성을 했을 때, 단지 언어의 차이만으로 시간 초과가 발생한다면..

같은 문제를 풀더라도 훨씬 더 빠른 알고리즘으로 접근해야한다는 말인가요?


언어가 아니라, 문제 해결 논리가 중요하다고 생각하고 있었는데

최근 몇번 동일한 알고리즘을 파이썬으로 작성하고 시간 초과를 받다보니ㅠㅠ 좀 허탈해서 넋두리를 해봤네요ㅠㅠㅠ


댓글 감사합니다~

redpigeon   4년 전

파이썬의 본질적인 한계는 어쩔 수 없군요..

https://www.acmicpc.net/blog/view/55

redpigeon   4년 전

17280번 같은 경우는 JAVA에서 TreeMap 클래스를 이용하면 통과할 수 있고(라고 들었습니다)

파이썬에는 정확히 동일한 자료 구조가 없어서, 적당히 딕셔너리+이진탐색으로 대체해 봤지만 Subtask 1까지만 가능했습니다.

이 경우가 이전 댓글에서 언급하신 '각 언어에서의 자료구조 구현 차이'겠지요..

물론 파이썬3로 정답을 제출한 분이 있는걸로 보아... 다른 접근 법이 있나봅니다.. 그냥 이건 제 실력이 미천한 탓인 걸로...


본 17278번에 대해서는 CPP 코드가 있습니다. (17280과 마찬가지로 제가 개인적으로 받은 코드라.. 게시판에 올리기는 뭐하네요, 작성자 분이 공개한것도 아닌지라..)

CPP코드에서도 특별한 라이브러리는 사용된것 없이, 단순히 std::array로 구현한 세그먼트 트리가 전부라 파이썬에서도 쉽게 구현이 가능했습니다만, Subtask 1만 통과할 수 있었습니다.


언어별로 조금 다른 자료 구조를 사용한 17280은 그렇다쳐도, 이 17278번에서는 정말 동일한 코드(라인 바이 라인으로 확인했습니다, 게다가 틀리지는 않으니.. 같겠죠..?)인데 통과를 못해서 이런 글을 적게 되었죠...


저도 그동안 파이썬 공부 삼아 대부분 파이썬으로만 문제를 풀어왔고, 백준의 다른 세그먼트 트리 문제나 여타 문제들에서 시간 초과의 경우는 없었기 때문에 좀 갸웃한 부분이 있었네요..

잘 알려지지 않은 문제다 보니 시간 조정 요구가 없어서 타이트한 그대로 유지되고 있는것인지... 흠...


별수 있나요.. 앞으로 공부를 좀 더 열심히 해보고 나중에 다시 풀어봐야지요!

답변을 딱히 기대하지 못했던 넋두리 글에 정성스럽게 답글 달아주셔서 정말 감사합니다~!

(아, 그리고 현업은 딱히 시간 제한이 요구되는건 아니지만, 이렇게 언어별로 성능 차이가 심하게 나타난다는게 부담이 된다는 뜻이었습니다. numpy 같은것만 사용 가능해도 훨씬 빠르게 되겠죠~)

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