배움과 성장/알고리즘·문제풀이
알고리즘 시간·메모리 제한 읽는 법: Python 복잡도와 실측 기준
알고리즘 문제의 제한은 입력 최댓값으로 가능한 복잡도를 먼저 좁히고, 최악 입력으로 실제 시간과 메모리를 재는 기준이다. “Python은 1초에 1억 번 연산한다”처럼 하나의 숫자로 통과 여부를 결정하면 자주 틀린다.같은 복잡도라도 채점 서버의 CPU, Python 구현과 버전, 연산 종류, 상수항, 입력 방식에 따라 실행 시간이 달라진다. 문제의 시간·메모리 제한과 언어별 보정도 채점 사이트마다 다르다.시간 제한은 이렇게 읽는다첫 단계는 입력 크기 N을 가능한 알고리즘의 최악 시간 복잡도에 대입하는 것이다.예를 들어 N = 200,000이라면 다음 차이는 이미 결정적이다.N²은 약 400억 번의 조합을 만든다.N log₂N은 약 352만 수준이다.N은 20만 수준이다.이 계산은 통과를 보장하는 속도표가..