[BOJ] 파이썬(Python) 주의사항 및 Tips

float, double 등의 부동소수점 자료형은 나타내는 수의 범위가 넓지만, 그 범위 안에 있는 모든 수를 정확하게 나타낼 수 있는 게 절대 아닙니다. 범위도 넓은데 원하는 수를 다 표현할 수도 있고 int만큼이나 빠르기까지 하면 그건 상상의 세계에 있는 자료형이죠.

반례 찾기

• 가장 중요한 것은 직접 데이터를 만들어서 넣어 보는 것입니다.
• 입력으로 1 이상 1,000,000 이하의 정수 N이 주어진다면 N=1, N=2 등으 ㅣ최소 케이스가 잘 나오는지 확인하는 것이 좋습니다.
  이런 입력이 특이 케이스가 되는 문제들이 종종 있고, 굳이 특이 케이스가 아니더라도 우리의 코드가 최소 케이스에서 틀릴 가능성은 얼마든지 있습니다.
• N=1,000,000 같은 최대 케이스를 넣었을 때 주어진 시간 제한 안에 답이 나오는지도 확인해 볼 수 있습니다. 답이 맞는지 확인하는 건 어떨까요? 문제에 따라 답을 손으로 알아내기 힘들 수도 있는데, 적어도 말이 되는 값은 나와야겠죠? 출력이 무조건 0 이상일 수 밖에 없는 문제에서 음수가 나오면 뭔가 잘못되었다는 뜻입니다.
• 매우 간단한 풀이가 있는데 시간복잡도가 너무 커서 못 쓰고, 그 대신 더 효율적인 풀이를 생각해봐야 하는 문제가 있습니다. 이런 문제는 다음 방법으로도 반례를 찾을 수 있습니다. 매우 간단한 풀이라면 구현하기 쉬워서 틀릴 가능성이 낮다는 점을 이용하는 방법입니다.

1. 매우 간단한 풀이를 작성한다.
2. 랜덤으로 데이터를 만든다.
3. 간단한 풀이와 틀린 풀이가 내놓는 답이 일치하는지 검사한다.
4. 2-3번을 반복한다.

알고리즘

• 배열 기반의 리스트(C++ vector, string, Java ArrayList, String, Python list, str, ...)의 중간에 뭔가를 끼워넣거나 빼는 것은 O(N)입니다.
• 퀵소트를 직접 구현하면 O(N^2)이 걸리는 데이터를 손쉽게 만들 수 있습니다. 그냥 내장된 정렬 함수를 쓰세요. 정렬을 직접 구현하는 것을 연습하시고자 한다면, 피벗을 랜덤으로 잡은 퀵소트를 구현하거나 힙소트, 머지소트 등 다른 O(nlogn) 정렬 알고리즘을 구현하는 방법이 있습니다.
• 격자에서 탐색할 때 범위 체크를 반드시 합시다.
• DP를 할 때에는 메모이제이션을 합시다. 안그러면 DP가 아닙니다.
• DFS는 절대로 최단거리를 구해주지 않습니다. 물론 메모이제이션 없이 모든 경로를 탐색하는 DFS는 최단거리를 구해주겠지만, 시간 초과가 날 것입니다.
• BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. BFS 문제에서 시간 초과나 메모리 초과가 나면 이것부터 의심해 보시면 됩니다.
• BFS를 할 때 큐의 크기가 제한되어 있도록 구현했다면, 그 크기는 적어도 방문할 수 있는 정점의 총 개수보다는 크게 합시다.

 

Python

Python2는 허점 투성이이고 2020년에 죽는 언어입니다. Python3를 사용합시다.

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

파이썬 입력 받기

import sys
num = sys.stdin.readline().strip()

그냥 input()으로 입력을 받을 때보다 속도가 빨라집니다.

10 Essential Python Tips

1. In-Place Swapping Of Two Numbers

x, y = 10, 20
print(x, y) # 10 20
x, y = y, x
print(x, y) # 20 10

 

2. Reversing a string in Python

a = "GeeksForGeeks"
print("Reverse is", a[::-1]) # Reverse is skeeGroFkeeG

 

3. Create a single string from all the elements in list

a = ["Geeks", "For", "Geeks"]
print(" ".join(a)) # Geeks For Geeks

 

4. Chaining Of Comparison Operators.

n = 10
result = 1 < n < 20
print(result) # True
result = 1 > n <= 9
print(result) # False

 

5. Use Of Enums in Python

class MyName:
    Geeks, For, Geeks = range(3)

print(MyName.Geeks) # 2
print(MyName.For) # 1
print(MyName.Geeks) # 2

 

6. Return Multiple Values From Functions

def x():
    return 1, 2, 3, 4
a, b, c, d = x()

print(a, b, c, d) # 1 2 3 4

 

7. Find The Most Frequent Value in A List.

test = [1, 2, 3, 4, 2, 2, 3, 1, 4, 4, 4]
print(max(set(test), key = test.count)) # 4

 

8. Check The Memory Usage Of An Object.

import sys
x = 1
print(sys.getsizeof(x)) # 28

 

9. Print string N times.

n = 2
a = "GeeksforGeeks"
print(a * n) # GeeksforGeeksGeeksforGeeks

 

10. Checking if two words are anagrams

from collections import Counter
def is_anagram(str1, str2):
    return Counter(str1) == Counter(str2)
print(is_anagram('geek', 'eegk')) # True

print(is_anagram('geek', 'peek')) # False

파이썬(Python) Tips and Tricks