[코딩테스트] 1. 시간복잡도 기본 개념

왜 시간복잡도를 알아야 할까

코딩테스트에서 "맞았습니다"와 "시간 초과" 사이의 차이는 대부분 알고리즘의 시간복잡도에서 갈린다. 같은 문제를 푸는 코드라도, 입력이 커지면 느린 알고리즘은 제한 시간 안에 끝나지 못한다.

시간복잡도를 이해하면 코드를 작성하기 전에 "이 접근법이 통과할 수 있는가?"를 판단할 수 있다. 즉, 풀이를 구현하기 전에 미리 걸러내는 필터 역할을 한다.

Big-O 표기법

Big-O는 입력 크기 N이 충분히 커졌을 때 알고리즘의 최악의 경우 연산 횟수가 어떤 비율로 증가하는지를 나타낸다.

핵심은 증가율이다. 상수나 낮은 차수의 항은 무시한다.

3N² + 5N + 100  →  O(N²)

• 3N² → 계수 3은 무시, N²만 남긴다
• 5N → N²에 비해 무시할 수 있는 크기이므로 제거
• 100 → 상수항 제거

왜 이렇게 단순화할까? N이 10일 때는 상수가 의미 있지만, N이 100,000이 되면 N²이 나머지를 압도하기 때문이다. 코딩테스트에서 관심 있는 건 "N이 최대일 때 시간 안에 끝나느냐"이므로, 지배적인 항만 보면 충분하다.

주요 복잡도 등급

아래 표는 N = 100,000일 때 대략적인 연산 횟수를 보여준다.

복잡도	이름	N = 100,000일 때 연산 횟수	흔한 예시
O(1)	상수	1	배열 인덱스 접근, HashMap 조회
O(log N)	로그	~17	이분 탐색
O(N)	선형	100,000	단순 반복, 슬라이딩 윈도우
O(N log N)	선형 로그	~1,700,000	정렬 (Arrays.sort), 우선순위 큐
O(N²)	이차	10,000,000,000	이중 for문
O(2^N)	지수	천문학적	부분집합 탐색
O(N!)	팩토리얼	천문학적	순열 탐색

O(N²)부터는 N이 10만만 돼도 100억 번 연산이 필요하다. Java 기준 1초에 대략 1~2억 번 연산이 가능하다고 보면, 이 정도면 시간 초과가 확정이다.

복잡도 성장률 비교

체감이 안 될 수 있으니 비유를 하나 들어보겠다.

N명의 학생이 있는 교실에서 출석을 부른다고 생각해보자.

• O(1): 학생 번호를 알고 있어서, 바로 그 자리를 보고 확인한다 → 학생이 몇 명이든 1번이면 끝
• O(log N): 학생이 번호순으로 앉아 있어서, 가운데를 확인하고 반씩 좁혀간다 → 1,000명이어도 10번이면 찾는다
• O(N): 처음부터 끝까지 한 명씩 부른다 → 학생 수만큼 시간이 걸린다
• O(N²): 모든 학생을 다른 모든 학생과 한 번씩 악수시킨다 → 학생 수의 제곱만큼 시간이 걸린다

코드에서 시간복잡도 읽는 법

단일 반복문 → O(N)

for (int i = 0; i < n; i++) {
    // O(1) 작업
}

반복 횟수가 N에 비례하므로 O(N)이다.

---

중첩 반복문 → O(N × M)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // O(1) 작업
    }
}

바깥 루프 N번 × 안쪽 루프 M번 = O(N × M)이다. N과 M이 같으면 O(N²).

---

반복문 안의 메서드 호출 → 숨은 복잡도 주의

for (int i = 0; i < n; i++) {
    int sum = IntStream.of(Arrays.copyOfRange(arr, i, i + k)).sum();
}

얼핏 보면 단일 반복문 같지만, 안쪽에서 Arrays.copyOfRange(O(K))와 sum(O(K))이 매번 실행된다. 실제 복잡도는 O(N × K)이다. 이런 숨은 복잡도가 시간 초과의 흔한 원인이다.

---

반씩 줄어드는 반복 → O(log N)

while (n > 0) {
    n /= 2;
}

매 반복마다 N이 절반으로 줄어드므로 O(log N)이다.

정리

핵심 포인트	설명
Big-O는 증가율	상수와 낮은 차수 항은 무시한다
지배적인 항만 남긴다	3N² + 5N → O(N²)
메서드 호출도 복잡도에 포함	Arrays.copyOfRange, String.substring 등은 O(N)
중첩 = 곱셈	바깥 루프 × 안쪽 루프

다음 문서에서는 이 개념을 바탕으로, 문제의 입력 크기와 시간 제한만 보고 어떤 복잡도까지 허용되는지 판단하는 법을 다룬다.