글 읽기 - 속도질문] 파이썬으로 제출했을 때 코드가 비슷해도 더 느려져서 실패하게되나요?

mimmyum 6년 전 0

BFS방식으로 풀었고, 다른 질문란에 있는 다른 분이 올린 코드와 비교했을 때 거의 동일하게 돌아가는 알고리즘 같은데,

파이썬으로 돌리면 20x20에서 굉장히 오랜 시간이 걸리더군요...

이게 제가 코딩을 잘못짜서 그런건가요? 어떤방식으로 개선할 수 있을까요... ㅠ.ㅠ

다른분이 올려주신 예시코드로 돌렸을 때 (C언어) 168MS 걸린 반면, 제코드로 돌리니 320MS가 나오네요...

이것도 중간에 야매코딩으로 넘겨서 이렇게 나온거고, 기본적으로는 시간초과가 나옵니다...

def DFS(total, x, y) :
    global map, sentence, maxtotal, dx, dy
    if total > maxtotal :
        maxtotal = total
    for i in range(4):
        newX = x + dx[i]
        newY = y + dy[i]

        if newX >= 0 and newX < R and newY >= 0 and newY < C:
            now = map[newX][newY]
            if sentence[ord(now) - 65] != 1:
                sentence[ord(now) - 65] = 1
                DFS(total+1, newX, newY)
                sentence[ord(now) - 65] = 0

if __name__ == "__main__" :
    R, C = [int(x) for x in input().split()]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    map = [0]*R
    maxtotal = 1
    for i in range(R) :
        temp = list(input())
        map[i] = temp
    sentence = [0]*26
    sentence[ord(map[0][0])-65] = 1
    DFS(1, 0 , 0)
    print(maxtotal)

djm03178 6년 전 0

파이썬은 그 특성상 C언어에 비해 매우 느릴 수밖에 없습니다.

그래서 BOJ에서는 https://www.acmicpc.net/help/l... 에 써있는 것처럼, 인터프리터나 스크립트 언어들에 대해서 시간 보너스를 제공하고 있고, 파이썬은 무려 +10초를 더 줍니다.

~~조만간 이 제한이 좀 더 빡세질 거라는 카더라가 있습니다.~~

jh05013 6년 전 0

파이썬이 기본적으로 매우 느린 언어입니다. 편의성과 프로그램 속도를 맞바꾸었다고 보시면 됩니다.

잘 돌아가야 하는데 시간초과가 나는 경우 Pypy로 제출하면 됩니다. 단 Pypy 3는 아직 믿을만한 속도를 못 내기 때문에 파이썬 2 문법으로 바꾸고 (대부분 그냥 input을 raw_input으로 바꾸기만 하면 됩니다) Pypy 2로 제출하는 것이 좋습니다.

mimmyum 6년 전 0

기본적으로 느린거는 알고있었는데 이렇게나 차이가 많이나는군요...

앞으로 시간 최적화부분에 신경을 좀 더 많이 써봐야겟네요 ㅠㅠ

답변 감사드립니다

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

문제

문제

출처

ICPC

속도질문] 파이썬으로 제출했을 때 코드가 비슷해도 더 느려져서 실패하게되나요?

mimmyum 6년 전 0

djm03178 6년 전 0

jh05013 6년 전 0

mimmyum 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말