알고리즘 시간·메모리 제한 읽는 법: Python 복잡도와 실측 기준

알고리즘 문제의 제한은 입력 최댓값으로 가능한 복잡도를 먼저 좁히고, 최악 입력으로 실제 시간과 메모리를 재는 기준이다. “Python은 1초에 1억 번 연산한다”처럼 하나의 숫자로 통과 여부를 결정하면 자주 틀린다.

같은 복잡도라도 채점 서버의 CPU, Python 구현과 버전, 연산 종류, 상수항, 입력 방식에 따라 실행 시간이 달라진다. 문제의 시간·메모리 제한과 언어별 보정도 채점 사이트마다 다르다.

시간 제한은 이렇게 읽는다

첫 단계는 입력 크기 N을 가능한 알고리즘의 최악 시간 복잡도에 대입하는 것이다.

예를 들어 N = 200,000이라면 다음 차이는 이미 결정적이다.

• N²은 약 400억 번의 조합을 만든다.
• N log₂N은 약 352만 수준이다.
• N은 20만 수준이다.

이 계산은 통과를 보장하는 속도표가 아니다. 후보를 빠르게 탈락시키는 1차 필터다. 그다음에는 실제 연산을 본다.

• Python loop인가, C로 구현된 built-in인가
• hashing, sorting, arbitrary-precision integer 연산이 들어가는가
• 같은 데이터를 여러 번 순회하는가
• 최악 입력에서 recursion이나 backtracking이 폭증하는가
• 입력 파싱과 출력량이 큰가

따라서 “O(N log N)이면 무조건 된다”가 아니라, 입력 상한과 상수항을 함께 보고 최악 입력을 직접 재는 편이 안전하다.

대표 입력으로 실행 시간을 재기

짧은 구간의 경과 시간은 wall clock보다 time.perf_counter()로 재는 것이 적절하다.

from random import Random
from time import perf_counter


def solve(values: list[int]) -> int:
    values.sort()
    return sum(values)


rng = Random(0)
data = [rng.randrange(1_000_000) for _ in range(200_000)]

started = perf_counter()
answer = solve(data)
elapsed = perf_counter() - started

print(answer, f"{elapsed:.3f}s")

한 번의 노트북 측정값을 채점 서버의 시간으로 그대로 환산할 수는 없다. 그래도 다음 비교에는 유용하다.

1. 평균 입력이 아니라 최댓값과 편향된 입력을 만든다.
2. 후보 알고리즘을 같은 데이터에서 비교한다.
3. 시작 비용과 반복 실행의 차이를 구분한다.
4. 제한에 간신히 맞는 구현보다 충분한 여유가 있는 복잡도를 선택한다.

입력이 매우 크다면 input()을 무조건 금지할 필요는 없지만, parsing이 병목일 때는 sys.stdin.buffer를 검토할 수 있다. 다만 O(N²) 알고리즘을 빠른 입력으로 구할 수는 없다.

import sys

numbers = map(int, sys.stdin.buffer.read().split())
total = sum(numbers)
print(total)

메모리 제한은 객체 수까지 계산한다

Python의 list는 값을 연속된 고정 크기 정수 배열로 저장하는 구조가 아니다. 대체로 object reference를 담고, 각 integer object의 공간이 별도로 필요하다. interpreter·build·값에 따라 크기가 달라지므로 “정수 하나는 항상 28바이트”라고 고정하면 안 된다.

sys.getsizeof()도 대상 객체 자체의 shallow size만 돌려준다. container가 가리키는 모든 객체의 크기를 자동으로 합산하지 않는다.

from sys import getsizeof

values = list(range(100_000))

print("list object:", getsizeof(values))
print("one int object:", getsizeof(values[0]))

실제 peak allocation의 변화를 볼 때는 tracemalloc을 쓸 수 있다.

import tracemalloc

tracemalloc.start()
values = [number * number for number in range(500_000)]
current, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()

print(f"current={current / 1024**2:.1f} MiB")
print(f"peak={peak / 1024**2:.1f} MiB")

tracemalloc은 Python이 추적하는 allocation을 보여 주며 운영체제가 보는 process RSS와 완전히 같지는 않다. 채점기는 보통 process의 최대 메모리를 자체 기준으로 측정하므로, 이 역시 비교와 조기 경고용으로 사용한다.

메모리가 빠듯하다면 다음 순서로 점검한다.

• 전체 입력을 보관하지 않고 streaming할 수 있는가
• 같은 의미의 list나 copy를 중복 생성하는가
• boolean 상태라면 bytearray로 표현할 수 있는가
• 고정 크기 숫자라면 array 같은 packed representation이 맞는가
• generator가 실제로 peak memory를 줄이는가

자료구조를 바꾸면 속도나 구현 복잡도가 달라진다. 메모리를 줄인다는 이유만으로 무조건 generator나 packed array를 쓰기보다 제한에 필요한 만큼만 바꾼다.

제출 전 판단 순서

1. N과 값의 범위, test case 수를 모두 확인한다.
2. 가능한 복잡도를 식으로 써서 비교한다.
3. 사용하는 자료구조의 개수와 copy 지점을 센다.
4. 최악 입력을 만들어 시간과 peak memory를 잰다.
5. recursion limit, integer 크기, I/O처럼 Python에 특화된 경계를 확인한다.
6. 채점 사이트의 현재 언어별 시간·메모리 규칙을 다시 읽는다.

핵심은 외운 연산 횟수가 아니라 복잡도로 후보를 좁히고, 실제 구현을 최악 조건에서 검증하는 것이다.

관련 풀이와 복잡도별 예시는 알고리즘·문제풀이 모음에서 이어서 확인할 수 있다.

자주 묻는 질문

Python은 1초에 몇 번 연산할 수 있나

모든 코드에 적용할 하나의 수치는 없다. Python loop, hash lookup, built-in sort, big integer 연산은 비용이 서로 다르고 실행 환경도 다르다. microbenchmark보다 전체 풀이를 대표 입력으로 재는 편이 낫다.

sys.getsizeof(list)로 전체 메모리를 알 수 있나

알 수 없다. list 자체의 shallow size만 보여 주며 참조 대상 객체의 크기는 포함하지 않는다. 구조를 이해한 추정과 peak measurement를 함께 사용해야 한다.

빠른 입력만 쓰면 시간 초과를 피할 수 있나

입출력이 병목일 때만 큰 차이가 난다. 알고리즘 복잡도가 제한에 맞지 않으면 입력 함수 변경만으로 해결되지 않는다.

참고 자료

• Python time.perf_counter
• Python sys.getsizeof
• Python tracemalloc
• 백준 온라인 저지 언어별 도움말