thnam91   7년 전

시간초과로 인해서 질문글에 있는 C 코드를 확인해보니 알고리즘 로직은 동일하다고 판단됩니다.

메모이제이션도 다이나믹 프로그래밍도 아닌 말 그대로 인덱스를 기반으로 x1, y1 부터 x2, y2까지 다 더하는 방식으로 구현했습니다.

질문 글을 확인하면 C 언어로 작성했을 경우 이상없이 통과한 듯 보이는데, 자꾸만 시간초과가 발생하네요.


파이썬에서 시간을 줄이기 위한 방법으로 input 함수를 sys.stdin.readline으로 변경도 했지만 여전히 시간초과가 발생하네요.

시간을 더 단축할 수 있는 방법이 있을까요? 알고리즘 자체를 메모이제이션이나 다른 방법을 통해서 접근해야할까요?

어렵지 않은 문제라고 생각했는데, 꽤나 까다롭네요.


추가적으로 질문하나 더 드리면, 가끔 타임라인 같은 곳에 남들이 제 코드를 봤다고 나오는데,

어떻게 다른 분들의 통과한 코드를 확인할 수 있나요? 어떤 탭을 눌러봐야 하는지 소스코드는 보이지가 않습니다.

된다면 질문글이 아니라 통과하신분의 코드 속에서 힌트를 얻을 수 있을텐데요.

sait2000   7년 전

Python으로 C랑 똑같은 로직을 구현했을 때 시간초과가 나면 받아들여야 합니다. 그냥 dp하시는 게 낫겠어요. 통과한 코드는 통과한 다음에 볼 수 있습니다. 통과하고 나면 맞은 사람 탭이나 숏코딩 탭에서 문제를 푼 언어 이름이 코드를 볼 수 있는 링크로 바뀌어요. 그런데 몇 번인가요.

thnam91   7년 전

제가 문제에 대한 번호를 입력안했었나 봅니다.

해당 문제는 2167번 문제, 2차원 배열의 합을 구하는 문제입니다.

cake_monotone   7년 전

파이썬이 매우 느리기 때문에, c로 아슬아슬하게 풀리는 로직도 파이썬으로는 터질 때가 많습니다.
그나마 대안이 있다면, 파이썬 코드를 pypy로 제출하는 건데, 이것도 한계가 있습니다 ㅜㅜ

위 코드에서 그나마 시간을 의미없이 잡아먹는 부분을 개선하자면

range
파이썬 2에서 range보다는 되도록 xrange를 사용하는 게 좋습니다.
메모리, 시간적 측면에서 더 이득입니다.

row = list(map(int, sys.stdin.readline().split()))

파이썬 2에서 map은 리스트를 반환합니다. 굳이 리스트를 리스트로 다시 변환할 필요는 없습니다


이 문제를 파이썬으로 푼 사람이 있는 걸 보면 다른 방법을 고민해보시는 것이 나을 것 같습니다.

thnam91   7년 전

답변감사합니다.

오늘은 xrange와 map의 리턴에 대해서 확실히 알게되었네요.

한 수 한 수 배워갑니다!

감사합니다!

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