yang000501   2년 전

분할정복 알고리즘을 공부하다가 해당 문제가 예시로 나와있어서 풀게 되었습니다.(다른 알고리즘의 풀이는 고려하지 않고 있는 상태입니다.)

해당 문제를 분할정복으로 풀 경우 시간 초과가 출력이 됩니다.

제가 계산 하였을 때는 최대 시간 복잡도가 9(재귀 개수)의 8승으로 1억보다 작은 것으로 파악 됩니다.

혹시 제 코드에서 수정해야 할 부분이나 시간 복잡도에 대한 제 이해의 틀린 부분이 있다면 조언부탁드립니다.^^

cozyyg   2년 전

아마 시간복잡도의 문제보다는 파이썬 입출력의 문제일 것 같습니다. print 함수를 적게 사용하는 것이 좋고, 출력량이 많은 경우에는 sys.stdout.write를 쓰는 것이 좋습니다.

아래 코드들을 참고해보세요.

yang000501   2년 전

감사합니다!

그런데 print를 sys.stdout.write로 수정해서 제출한 경우에도 시간초과가 출력이 되네요.....

아마 알고리즘 자체의 문제같긴 한데 어느 부분을 수정해야될지는 모르겠네요ㅜㅜ

cozyyg   2년 전

그러면 아마 크기가 큰 list를 다루는 게 문제일 것 같습니다... list 접근 자체가 좀 오래 걸리는 편이라... 함수 호출이 많이 되는 것도 문제일 수 있을 것 같네요.

파이썬이 오래 걸리는 이유는 다양하고 알기 힘들어서 어떤 부분이 문제인지 알기는 쉽지 않습니다. 참고로 string이나 list의 +를 이용하는 풀이들은 여유롭게 통과합니다.

yang000501   2년 전

네 저도 한번 고민을 해봐야 겠네요..

답변 감사합니다!!

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