반응형
float, double 등의 부동소수점 자료형은 나타내는 수의 범위가 넓지만, 그 범위 안에 있는 모든 수를 정확하게 나타낼 수 있는 게 절대 아닙니다. 범위도 넓은데 원하는 수를 다 표현할 수도 있고 int만큼이나 빠르기까지 하면 그건 상상의 세계에 있는 자료형이죠.
반례 찾기
- 가장 중요한 것은 직접 데이터를 만들어서 넣어 보는 것입니다.
- 입력으로 1 이상 1,000,000 이하의 정수 N이 주어진다면 N=1, N=2 등으 ㅣ최소 케이스가 잘 나오는지 확인하는 것이 좋습니다.
이런 입력이 특이 케이스가 되는 문제들이 종종 있고, 굳이 특이 케이스가 아니더라도 우리의 코드가 최소 케이스에서 틀릴 가능성은 얼마든지 있습니다. - N=1,000,000 같은 최대 케이스를 넣었을 때 주어진 시간 제한 안에 답이 나오는지도 확인해 볼 수 있습니다. 답이 맞는지 확인하는 건 어떨까요? 문제에 따라 답을 손으로 알아내기 힘들 수도 있는데, 적어도 말이 되는 값은 나와야겠죠? 출력이 무조건 0 이상일 수 밖에 없는 문제에서 음수가 나오면 뭔가 잘못되었다는 뜻입니다.
- 매우 간단한 풀이가 있는데 시간복잡도가 너무 커서 못 쓰고, 그 대신 더 효율적인 풀이를 생각해봐야 하는 문제가 있습니다. 이런 문제는 다음 방법으로도 반례를 찾을 수 있습니다. 매우 간단한 풀이라면 구현하기 쉬워서 틀릴 가능성이 낮다는 점을 이용하는 방법입니다.
- 매우 간단한 풀이를 작성한다.
- 랜덤으로 데이터를 만든다.
- 간단한 풀이와 틀린 풀이가 내놓는 답이 일치하는지 검사한다.
- 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
반응형
'DEVLOG > Algorithms' 카테고리의 다른 글
[BOJ 11047] 동전 0 파이썬 풀이 (0) | 2019.09.03 |
---|---|
[BOJ 11399] ATM 파이썬(Python) 풀이 (0) | 2019.09.03 |
[알고리즘] 추천 자료 모음 - 블로그, 유튜브 강의 (1) | 2019.08.29 |
[BOJ 1920] 수 찾기 파이썬 풀이 (0) | 2019.08.28 |
코딩 인터뷰 핵심 자료구조 - 해시 테이블(Hash Table) (0) | 2019.08.28 |
댓글