[코딩테스트] 2. 입력 크기로 허용 복잡도 판단하기

문제를 열자마자 봐야 할 세 가지

코딩테스트 문제를 열면, 코드를 작성하기 전에 반드시 세 가지를 확인해야 한다.

1. 시간 제한 (보통 1~2초)
2. 메모리 제한 (보통 128~512MB)
3. 입력 범위 (N, M 등의 최대값)

이 세 가지 조합이 어떤 알고리즘을 써야 하는지를 알려준다. 풀이를 떠올리기 전에, 허용되는 시간복잡도의 상한선부터 정하는 것이 핵심이다.

Java 기준 연산 횟수 감각

경험적으로 Java는 1초에 약 1~2억 번의 단순 연산(덧셈, 비교, 대입 등)을 수행할 수 있다. 이 숫자를 기준으로 삼으면 된다.

시간 제한이 2초라면? 단순히 2억 번까지 허용된다고 보면 된다.

입력 크기별 허용 복잡도 표

이 표가 코딩테스트의 치트시트다. 문제를 읽고 N의 범위를 확인하면, 아래 표에서 어떤 복잡도까지 사용할 수 있는지 바로 판단할 수 있다.

N의 범위	허용 복잡도	대표 알고리즘
N ≤ 10	O(N!)	브루트포스, 순열 탐색
N ≤ 20~25	O(2^N)	부분집합, 비트마스킹
N ≤ 500	O(N³)	플로이드-워셜, 3중 루프
N ≤ 5,000	O(N²)	이중 루프, 삽입 정렬
N ≤ 100,000	O(N log N)	정렬, 우선순위 큐
N ≤ 1,000,000	O(N)	슬라이딩 윈도우, 투 포인터, 누적합
N ≤ 100,000,000	O(log N) ~ O(√N)	이분 탐색, 수학

표 읽는 법

N ≤ 250,000인 문제가 있다고 하자. 표에서 100,000과 1,000,000 사이에 위치하므로 O(N log N)이나 O(N) 알고리즘이 필요하다.

만약 여기서 O(N²) 풀이를 쓰면? 250,000² = 625억 번 연산이므로, 1초는커녕 수백 초가 걸린다. 시간 초과 확정이다.

연산 횟수 계산 실전 연습

구체적인 문제로 연습해보자.

예시 1: BOJ 21921 블로그

시간 제한: 1초
N ≤ 250,000
X ≤ N

이중 for문(O(N × X))을 쓰면 최악의 경우 얼마나 걸릴까?

N = 250,000, X = 125,000 (N/2)일 때
연산 횟수 ≈ 250,000 × 125,000 = 31,250,000,000 (약 312억)

1초에 1억 번 처리 가능하므로, 약 312초가 걸린다. 당연히 시간 초과다.

O(N) 풀이(슬라이딩 윈도우)를 쓰면?

연산 횟수 ≈ 250,000

1억의 0.25%도 안 된다. 여유롭게 통과한다.

---

예시 2: N ≤ 5,000인 문제

시간 제한: 2초
N ≤ 5,000

O(N²) = 25,000,000 (2,500만). 2초 제한이면 2억까지 가능하니 충분히 통과한다.

O(N³) = 125,000,000,000 (1,250억). 절대 불가능하다.

메모리 제한 판단법

시간만큼 자주 걸리진 않지만, 메모리 초과도 흔한 실패 원인이다.

Java의 메모리 사용량 기준

자료형	크기
int	4 bytes
long	8 bytes
int[] (길이 N)	약 4N bytes
int[][] (N × M)	약 4NM bytes

메모리 초과가 나는 흔한 패턴

반복문 안에서 매번 새로운 배열을 생성하는 경우다.

for (int i = 0; i < n; i++) {
    int[] copy = Arrays.copyOfRange(arr, i, i + k);  // 매번 새 배열 생성
    int sum = IntStream.of(copy).sum();
}

이 코드는 루프가 돌 때마다 크기 K짜리 배열을 새로 만든다. GC(가비지 컬렉션)가 제때 수거하지 못하면, N × K × 4 bytes만큼의 메모리가 누적될 수 있다. N과 K가 크면 메모리 초과로 이어진다.

해결책은 새 배열을 만들지 않는 것이다. 슬라이딩 윈도우처럼 기존 값을 빼고 새 값을 더하는 방식으로 바꾸면 추가 메모리 없이 O(1) 공간으로 처리할 수 있다.

복잡도별 대표 알고리즘 정리

어떤 복잡도가 필요한지 알았다면, 그 복잡도에 맞는 알고리즘을 떠올려야 한다.

복잡도	대표 알고리즘	언제 의심할까
O(N)	슬라이딩 윈도우, 투 포인터, 누적합	"연속 구간의 합/최대" 문제
O(N)	스택, 큐	"괄호 짝 맞추기", "다음 큰 수"
O(N log N)	정렬 후 탐색, 이분 탐색	"정렬하면 풀리는" 문제
O(N log N)	우선순위 큐, 트리	"최소/최대를 반복적으로 꺼내는" 문제
O(N²)	DP(2차원), 이중 루프	N ≤ 5,000이고 모든 쌍 비교
O(V + E)	BFS, DFS	그래프 탐색

판단 프로세스 요약

문제를 읽은 직후, 코드를 쓰기 전에 아래 순서를 따른다.

다음 문서에서는 실제로 시간 초과와 메모리 초과를 경험했던 문제를 가지고, 이 판단 프로세스를 어떻게 적용하는지 분석한다.