알고리즘을 풀때 우리를 괴롭히는 3대장이 있다.. 1)시간초과 2)반례 3)메모리초과이다. 사실 반례는 열심히 생각해내야해서 답이 없고... 시간초과는 입력값과 내 코드를 기반으로 해서 시간복잡도를 구하면 대충 계산해볼 수 있다. 메모리 초과도 마찬가지. 그래서 자신의 코드를 기반으로 시간초과 여부를 계산해보는 방법을 정리해보도록 하자.
시간 초과 계산하기
우선 선행되어야할것은 내 코드의 시간복잡도 구하기다. 시간복잡도는 O(N), O(N^2)... 등 다양하고, 말 그대로 코드가 몇 번 반복되는지를 구한 후 상수는 제거해주면 된다. 말보다는 예시를 보고 계산해보자.
for i in range(N):
for j in range(N):
print(i+j)이 코드는 outer for문이 N번, inner for문이 N번 도니까 시간복잡도가 O(N^2)다.
i=1
while(i<n):
i=i*2이 코드는 임의의 N이 되기까지 i를 2씩 곱해주면서 2,4,8, ... 2의 거듭제곱으로 N에 도달할때까지 while문이 돌아간다. 따라서 시간 복잡도는 O(logN)이다.
def fibo(n):
if(n<=1):
return n
return fibo(n-1)+fibo(n-2)
fibo(n)이 코드는 한 번의 호출에 두 번의 호출이 가지처럼 뻗어져나간다. (조금 다를 순 있지만, 트리 형식을 생각해보자) 따라서 O(2^N)가 될 것이다.
우리가 지금 알아보려는 건 시간 복잡도가 아니고 시간 복잡도를 활용해서 알고리즘을 제한 시간 안에 풀도록 하는 것이다. 사실 시간 복잡도만으로는 실행 시간을 완벽하게 계산할 수가 없다. 시간 복잡도부터가 러프한 값인데 실행 시간 또한 실행 환경에 따라 다르고, 각각을 세밀하게 계산할 수가 없기 때문이다. 그래도 대충 이게 시간 초과가 날지 안날지, 이 정도 입력값이면 어떤 풀이를 써야할지 정도를 어림짐작할 수는 있다. 정확한 값은 알 수 없지만... 그냥 필자의 환경에서 테스트를 해봤다.
import time
start_time = time.time()
result = 0
for i in range(10000):
result+=i
end_time = time.time()
execution_time = end_time - start_time
print(execution_time)해당 코드는 O(N)이고 N=10^4일때다. 0.8밀리초정도 나왔다.
N=10^5으로 바꾸니 8밀리초정도 나왔다. N=10^6은 0.1초 정도, N=10^7이 0.9 - 1초, N=10^8(1억)이 10초 정도 나왔다.
import time
start_time = time.time()
sum=0
i = 10**8
while i>0:
i//=2
end_time = time.time()
execution_time = end_time - start_time
print(execution_time)
해당 코드는 O(logN)이고 N=10^8(1억)일때다. 4마이크로초정도 나온다. 사실상 logN이면 시간 초과 걱정은 안 해도 되는거다(...)
import time
start_time = time.time()
sum=0
n = 10**3
for i in range(n):
for j in range(n):
sum=i+j
end_time = time.time()
execution_time = end_time - start_time
print(execution_time)해당 코드는 O(N^2)이고 N=10^3일때다. 이때 1초정도 소요됐다. N=10^4일때 10초정도 소요됐다.
1초당 연산 횟수는 대략 1억(10^8)번이다. (python: 2천만 번 정도)
제한시간이 1초일 때,
입력이 10,000,000 개의 경우: O(N) 알고리즘
입력이 100,000 개인 경우: O(N * log N) 알고리즘
입력이 2,000 개인 경우: O(N * N) 알고리즘
입력이 500개: O(N * N * N) 알고리즘<이것이 코딩테스트다>에 따르면 이렇다고 한다. 실험 했던 것과 대략 비슷해 보인다. 이걸 대충 유념해두고 문제 풀면 될 것 같다.
메모리 초과 계산하기
요새는 메모리가 빡센 문제는 별로 없긴 하지만... 메모리의 경우 대충 다음과 같다.
int 1,000개 : 4KB
int 1,000,000개: 4MB
int 10,000,000개: 40MB이 정도다. int는 4바이트니까... 하지만 뭔가 이상하다. 백준 2096번: 내려가기의 경우, 입력값의 최대 입력줄이 10만이고 각 줄마다 3개씩 들어오므로 최대 30만개를 저장하게 되는데, 파이썬에서는 입력값을 전부 저장만해도 메모리초과가 떴다. 이 글을 쓰게 된 계기다... 알고보니 파이썬의 경우 int형이 28바이트에서 시작한다고 한다(...) 그래서 4MB인 경우 파이썬은 int 14만개 정도 저장할 수 있는 거고, 당연히 메모리 초과가 발생한거다. 시간복잡도에 비해 공간복잡도는 계산하기가 복잡하다. 파이썬인 경우에는 더 그렇다. 사실 요새 보통은 문제에서 메모리 한도는 128MB정도로 주는데, python 기준으로 int형을 450만개 정도 저장할 수 있다고 보면 된다. 그러니까 보통은 크게 신경쓸 필요가 없고... 4MB나 2MB 이런식으로 극단적으로 공간을 넉넉하지 않게 주는 경우에만 이런 부분을 신경써서 계산하면 된다. (공간을 절약해서 풀이하는 알고리즘으로 슬라이딩 윈도우가 있다. 해당 문제도 슬라이딩 윈도우 방법으로 풀면 된다.)
