https://www.acmicpc.net/blog/view/55
https://www.acmicpc.net/blog/view/70
백준 단계별 풀어보기를 하다 발견한 팁을 정리했다.
sys.stdin.readline
Python은 편리성을 위해 속도를 많이 희생한 언어이기 때문에, 입출력 시간을 조금이라도 줄여야한다.
아래는 input 대신 사용하여 더 빨리 입력할 수 있는 방법이다.
import sys
input = sys.stdin.readline # sys.stdin.readline이 길기 때문에 이렇게 짧게 사용할 수 있다.
T = int(input())
A, B = map(int, input().split())
...BOJ 작동 관련
- 45.0 이 올바른 출력인데, 45 또는 45.00 등을 출력하면 틀린 답이 된다. 단, 일부
스페셜 저지가 있는 문제의 경우 오차가 정해져있어, 오차 이내라면 정확한 값이 아니라도 올바른 답이 될 수 있다. - 입력을 다 받은 뒤 출력할 필요가 없다. 입력 파일과 출력 파일은 분리되어있으므로, 중간중간 출력해도 결과만 맞으면 된다.
- 시간 초과 : 백준 문제에는 여러개의 예제파일이 주어지는데, 여기서 시간은 출력에 가장 오래 걸린 파일을 기준으로 한다. 여러 파일중 하나라도 제한 시간을 초과하면 시간 초과이다.
- 메모리 초과 : 마찬가지로 한 순간이라도 지정된 메모리를 초과하면 메모리 초과이다.
- 맞아야 하는 코드인데 틀렸다고 뜨는 경우는 없다. 항상 자신의 잘못부터 의심하자.
- 파이썬은 제대로 된 풀이여도 시간 초과가 발생할 수 있다. 이 때는 Pypy로 제출할 경우 어지간하면 풀 수 있다. (일부 못푸는 문제도 있다는 것을 명심)
자주 틀리는 요인
- 부동소수점의 경우 수를 정확하게 나타내는 데 한계가 있다. 항상 오차를 조심해야한다.
- Null과 공백은 엄연히 다른 문자이다. Null을 출력해야하는데 공백을 출력하거나, 그 반대의 경우 틀린 출력이 된다.
- 나눗셈에 음수가 들어갈 경우 결과는 언어별로 다르다.
- Python의 경우 음수 나눗셈의 반올림은 작아지는 쪽으로 이루어진다.
파이썬 관련
- 파이썬의 input은 항상 문자열로 처리되므로, 수 비교가 필요할 때는
int()를 통해 정수로 형변환하자 is키워드는 두 대상이 값이 같은지가 아니라, 완전히 같은 대상을 가리키는지를 비교한다. 백준에서 이걸 쓸일은 거의 없다.- list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등의 list 연산은 전부 O(N)의 시간 복잡도를 갖는다.(링크참조 : https://wiki.python.org/moin/TimeComplexity)
- 위의 이유로 list를 큐 또는 덱으로 사용하면 절대절대절대 안된다!!!! 반드시
collections.deque를 사용하자
-> 사실 아직 무슨말인지 모르겠다... 공부하자 ㅠㅠ - 파이썬의 재귀 깊이 기본값은 1,000이다.
sys.setrecursionlimit를 통해 재귀 깊이 조절이 가능하다.
pypy 관련
- pypy 정도로 대부분의 문제는 풀리지만 solved.ac 기준 플래티넘부터는 위험해지기 시작한다. 상황에 맞는 언어를 사용하자
- print를 사용할 경우
sys.stdout.write보다 많은 메모리를 사용하게 된다. sys.setrecursionlimit에서 재귀깊이를 크게 할 수록 메모리를 많이 사용한다.
