rmm1   1년 전

일단 맞기는 했는데... 실행시간이 6초 정도로 너무 길더라구요.

그런데 속도 저하가 발생하는 부분이 어딘지는 짐작이 되는데 수정할 방법을 모르겠어서요. 

어디를 어떻게 수정해야 할까요?

djm03178   1년 전

PyPy3로 제출하시면 훠어어어어어얼씬 빠릅니다.

코드상에 딱히 문제는 없습니다. 그냥 Python 3가 원래 그만큼 느릴 뿐입니다.

bamgoesn   1년 전

djm님 말씀대로 Pypy3로 제출하시면 훨씬 빠른 걸 보실 수 있을 겁니다. 다만 dfs 함수에서 최적화의 여지가 좀 보여서 좀 말씀드리려고 합니다.

dfs 함수에서는 루프문 중간에 u not in visited가 반복적으로 이뤄집니다. 길이 n인 리스트에 대해 in 연산자를 통해 원소가 있는지 없는지 판단하는 것은 시간복잡도가 O(n)입니다. 이 함수 안에선 visited에 원소를 추가하고, 그 안에 값이 있는지 없는지 판단하는 것이 반복적으로 이뤄지므로 집합 자료형을 사용하면 더 효율적으로 visited 안에 u가 있는지 없는지를 확인할 수 있습니다.

덤으로 stack이 리스트인 만큼 u not in stack 역시 속도를 늦추는 원인입니다. 이는 stack 외에 stack_set = set(stack) 변수를 추가로 만들어서 stack과 동기화시킨 채로 관리함으로써 해결할 수 있습니다. stack.append(u)를 할 때마다 stack_set.add(u)를 하고, v = stack.pop()을 할 때마다 stack_set.remove(v)를 하고, u not in stack 대신 u not in stack_set을 사용하면, 리스트가 유리할 땐 리스트를 쓰고 집합이 유리할 땐 집합을 쓰게 됩니다.

이걸 적용하시면 Python 3 기준 900ms 정도, Pypy3 기준 460ms 정도로 시간이 확 줄어듭니다. 코드가 많이 느리다 싶을 땐 시간복잡도에 기반해서 어디에서 병목이 발생하는지 확인하시면 최적화에 도움이 됩니다.

bamgoesn   1년 전

추가: dfs 함수 안에서 graph[v] = []를 해주는 덕분에 stack을 사용한 최적화는 엄청 큰 영향을 주는 건 아닌 것으로 보입니다. stack 최적화를 적용하지 않아도 Pypy3 기준 600ms정도는 나옵니다.

rmm1   1년 전

아하... set도 O(n)인 줄 알았는데 더 빠른가보네요
말씀하신 대로 수정해보겠습니다. 그리고 앞으로는 PyPy3으로도 해봐야겠네요.
답변 감사합니다.

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