python - 코딩테스트 요인

백준에서 "자주 틀리는 요인"으로 정리해 둔 부분에서 python만 추렸습니다.

 

Python과 Pypy

• 파이썬 2를 쓰면 안 됩니다. 코드가 틀린 건 아니지만, 언어가 틀렸습니다.
• • BOJ는 numpy 등 외장모듈을 지원하지 않습니다. (사실 모든 언어가 그렇습니다.)
• 풀이가 분명히 맞고 시간복잡도도 충분히 작은데 시간 초과가 난다면 언어를 Pypy로 설정하고 제출하면 됩니다. 파이썬은 원래 편리성과 속도를 맞바꾼 언어이기 때문에, 맞아야 될 풀이가 시간 초과더라도 이상할 게 전혀 없습니다.
• 두 수를 입력받고 나서 비교할 때는 반드시 int로 변환을 합시다. 문자열의 비교는 사전 순 비교이기 때문에, 3은 10보다 작지만 "3"은 "10"보다 큽니다.
• is 키워드는 두 대상의 값이 같은지가 아니라 완전히 같은 대상을 가리키는지를 비교합니다. BOJ에서 이걸 쓸 일은 거의 없습니다. 같은 "hello"더라도 따로 정의하면 다른 대상이 됩니다. 이걸 쓰면 디버깅하기도 힘든 게, -5 이상 255 이하의 int는 미리 만들어 놓고 정의할 때마다 가져다 쓰기 때문에, 딱 그 범위까지는 is와 ==가 똑같은 동작을 합니다. 그래서 손으로 반례를 찾으려고 하면 찾아지지 않습니다.
• list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다. 이외에도 O(N)이 걸리는 list 연산이 굉장히 많습니다. https://wiki.python.org/moin/TimeComplexity
• 위의 이유로, list를 큐 또는 덱으로 사용하면 절대, 절대, 절대, 절대, 절대 안 됩니다!! 반드시 collections.deque를 써야 합니다.
• 아니요, queue.Queue도 안 됩니다. 이건 멀티스레딩을 위해 만들어진 큐이고 매우 느립니다. 심지어 BOJ의 Python은 queue 모듈 자체가 없는 것 같습니다.
• 파이썬의 재귀 깊이는 기본적으로 최대 1,000입니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다.
• 두 개의 int를 나누면 float이 됩니다. int(a/b) 말고 a//b를 쓰는 것이 훨씬 안전합니다. 맨 위의 "부동소수점 자료형은 나타내는 수의 범위가 넓지만 ..."을 읽어보세요.

Pypy만

일반 Python에는 해당되지 않는 사항입니다.

• 사실 Pypy가 시간 초과더라도 이상할 건 전혀 없습니다. 쉬운 문제들은 거의 다 Pypy로 충분히 풀리지만, solved.ac 플래티넘 정도의 문제부터는 조금씩 위험해지기 시작합니다. 상황에 맞는 언어를 사용하도록 합시다.
• 현재 BOJ의 Pypy에는 exit이 없어서 sys.exit을 사용해야 합니다. BOJ에서만 보이는 현상으로 알고 있어서 왜 그렇게 되었는지는 모르겠으나, 일반적으로 sys.exit을 사용하는 것이 더 바람직한 코딩 스타일입니다. (관련 링크)
• Pypy의 재귀 깊이는 파이썬과 달리 딱 정해 놓은 제한이 없습니다. 하지만 10만 단위로 너무 깊이 들어가면 스택 오버플로가 나고, 그 제한은 파이썬보다 낮습니다. 또한 Pypy는 재귀에 굉장히 약합니다.
• print가 sys.stdout.write보다 많은 메모리를 차지합니다. 구체적으로, print를 많이 사용할 수록 메모리도 많이 사용됩니다. 2020년 8월 9일 현재 Atcoder에서도 같은 현상이 나는 것으로 확인했습니다.
• sys.setrecursionlimit에서 설정해 놓은 재귀 깊이가 클 수록 메모리 사용량도 큽니다. 2020년 8월 9일 현재 Codeforces에서도 같은 현상이 나는 것으로 확인했습니다.

 

 

참고 : https://www.acmicpc.net/blog/view/55
원문 : https://www.acmicpc.net/blog/view/70