2강. 빅오 표기 자세히 | 코딩 테스트 합격 알고리즘 30강 · 중급 — 누구나패스

🎯 학습 목표

1강에서 빅오를 직관적으로 익혔습니다. 이 강을 마치면 코드를 보고 복잡도를 셀 수 있게 됩니다. 반복문이 몇 겹인지, 반복 횟수가 어떻게 줄어드는지를 근거로 O(1)·O(log n)·O(n)·O(n log n)·O(n²)를 구분하고, 최선·평균·최악의 차이도 설명할 수 있게 됩니다.

그리고 가장 실용적인 기술 하나를 익힙니다. 문제의 입력 범위만 보고 "어떤 복잡도로 풀어야 하는지" 역산하는 것입니다.

💡 복잡도를 세는 세 가지 규칙

코드에서 복잡도를 셀 때는 "이 줄이 총 몇 번 실행되는가"만 따지면 됩니다. 규칙은 세 개뿐입니다.

규칙 1 — 순차 실행은 더한다. 반복문 두 개가 나란히 있으면 n + n = 2n이고, 상수를 버리면 O(n)입니다.

규칙 2 — 중첩 실행은 곱한다. 반복문 안에 반복문이 있으면 n × n = n²이므로 O(n²)입니다.

규칙 3 — 가장 큰 항만 남긴다. n² + n은 O(n²)입니다.

패턴별 복잡도 세기

  ① 단일 반복문
     for i in range(n):        ← n번
         (상수 시간 작업)
     ─────────────────────────  O(n)

  ② 중첩 반복문
     for i in range(n):        ← n번
         for j in range(n):    ← 각각 n번
             (상수 시간 작업)
     ─────────────────────────  O(n × n) = O(n²)

  ③ 나란한 반복문
     for i in range(n): ...    ← n번
     for j in range(n): ...    ← n번
     ─────────────────────────  O(n + n) = O(n)

  ④ 안쪽이 i에 따라 줄어드는 중첩
     for i in range(n):
         for j in range(i, n): ← n, n-1, n-2, ... 1번
     ─────────────────────────  대략 n²/2 → O(n²)
     ※ 절반이어도 상수는 버리므로 O(n²)다

  ⑤ 반복마다 절반으로 줄어듦
     while n > 1:
         n = n // 2            ← n → n/2 → n/4 → ... → 1
     ─────────────────────────  O(log n)

  ⑥ 바깥은 n번, 안쪽은 절반씩
     for i in range(n):        ← n번
         (절반씩 줄이는 작업)   ← 각각 log n번
     ─────────────────────────  O(n log n)

⑤가 왜 O(log n)인지 짚고 넘어가겠습니다. n을 계속 절반으로 나눠 1이 될 때까지 몇 번 나눠야 하는지를 묻는 것입니다. n이 1,024라면 1024 → 512 → 256 → … → 1로 10번입니다. 2를 10번 곱하면 1,024이므로, 이 횟수가 바로 밑이 2인 로그입니다.

여기서 로그의 위력이 나옵니다. n이 100만이어도 약 20번이면 끝납니다. 입력이 1,000배가 되어도 횟수는 10번 늘어날 뿐입니다.

📖 최선·평균·최악, 그리고 상각

같은 알고리즘이라도 입력이 어떻게 생겼느냐에 따라 걸리는 시간이 달라집니다. 그래서 복잡도는 세 가지로 나눠 말합니다.

구분	의미	리스트에서 값 찾기 예
최선 (Best)	가장 운이 좋을 때	맨 앞에서 찾음 → O(1)
평균 (Average)	보통의 경우	절반쯤에서 찾음 → O(n)
최악 (Worst)	가장 불리할 때	맨 끝이거나 없음 → O(n)

코딩 테스트에서는 최악을 기준으로 판단합니다. 출제자는 대개 가장 불리한 입력을 테스트 케이스에 넣어 두기 때문입니다. "평균적으로는 빠른데요"라는 항변은 통하지 않습니다.

여기에 상각(amortized) 복잡도라는 개념이 하나 더 있습니다. 대부분은 빠른데 가끔 느린 작업이 섞일 때, 전체를 평균 내서 보는 방식입니다.

파이썬 리스트의 append가 대표적입니다. 보통은 O(1)로 끝나지만, 내부 공간이 꽉 차면 더 큰 공간을 새로 잡아 기존 원소를 전부 옮깁니다. 그 순간만 O(n)입니다. 그런데 이 재할당은 드물게 일어나므로, n번 append한 총비용을 n으로 나누면 O(1)이 됩니다. 이것을 "상각 O(1)"이라고 합니다.

1강의 표에서 append가 O(1)로 적혀 있던 이유가 이것입니다. 매번 O(1)이라는 뜻이 아니라, 길게 보면 평균 O(1)이라는 뜻입니다.

💻 실전 예제 — 복잡도를 눈으로 확인하기

세 가지 복잡도의 실행 횟수를 직접 세어 보겠습니다.

def count_linear(n):
    """O(n) : 반복문 한 겹"""
    steps = 0
    for i in range(n):
        steps += 1                  # 이 줄이 n번 실행된다
    return steps


def count_quadratic(n):
    """O(n^2) : 반복문 두 겹"""
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1              # n * n 번 실행된다
    return steps


def count_log(n):
    """O(log n) : 매번 절반으로 줄인다"""
    steps = 0
    while n > 1:
        n = n // 2                  # 정수 나눗셈으로 절반
        steps += 1
    return steps


for n in [10, 100, 1000]:
    print(n, count_linear(n), count_quadratic(n), count_log(n))

코드를 줄 단위로 보겠습니다.

steps += 1 — 실제 계산 대신 실행 횟수만 세는 장치입니다. 복잡도를 눈으로 확인하는 데 유용합니다.
for i in range(n) — range(n)은 0부터 n-1까지이므로 정확히 n번 반복합니다.
for j in range(n) — 바깥 반복 한 번마다 n번 돕니다. 그래서 총 n × n번입니다.
n = n // 2 — //는 몫만 남기는 나눗셈입니다. 7 // 2는 3입니다. 1이 될 때까지 절반씩 줄이므로 반복 횟수가 log n에 비례합니다.
세 함수 모두 변수 몇 개만 쓰므로 공간 복잡도는 O(1)입니다.

실행하면 다음과 같이 나옵니다.

n        O(n)      O(n²)        O(log n)
────────────────────────────────────────
10         10         100            3
100       100      10,000            6
1,000   1,000   1,000,000            9

  ▲ n이 100배가 될 때
    O(n)     은 100배
    O(n²)    은 10,000배
    O(log n) 은 6 → 9, 겨우 3 증가

  ※ 파이썬은 큰 n에서 O(n²) 실행이 매우 오래 걸린다.
    n=1000까지만 시험해 보는 것을 권한다.

이 표가 알고리즘 공부의 이유를 한 장으로 보여 줍니다. 복잡도를 한 단계 낮추는 것이 컴퓨터를 바꾸는 것보다 훨씬 큰 효과를 냅니다.

🧭 입력 범위로 복잡도 역산하기

이제 가장 실용적인 기술입니다. 문제에 적힌 n의 최대값을 보면 어떤 복잡도까지 허용되는지 대략 알 수 있습니다.

n의 최대 범위	노려야 할 복잡도	대표 접근
n ≤ 20 안팎	O(2ⁿ), O(n!)도 가능	완전 탐색·백트래킹
n ≤ 1,000 안팎	O(n²)	이중 반복문·기본 DP
n ≤ 100,000 안팎	O(n log n)	정렬·이분 탐색
n ≤ 1,000,000 이상	O(n) 또는 O(log n)	한 번 훑기·수학적 접근

이 표는 정확한 규칙이 아니라 어림잡는 기준입니다. 연산의 종류, 채점 환경, 언어에 따라 달라지므로 여유를 두고 판단해야 합니다. 특히 파이썬은 다른 언어보다 느린 편이라 경계선에 있는 풀이는 통과를 장담하기 어렵습니다.

그래도 이 감각이 있으면 풀이 방향을 빨리 좁힐 수 있습니다. n이 100,000인데 이중 반복문이 떠올랐다면, 그 방향은 접고 정렬이나 이분 탐색을 쓸 수 있는지부터 고민하는 것이 맞습니다.

⚠️ 자주 하는 실수

첫째, 내장 함수의 복잡도를 0으로 칩니다. sorted()는 O(n log n)이고, 리스트의 in은 O(n)이며, max()도 O(n)입니다. 반복문 안에 이런 함수가 들어가면 전체 복잡도가 곱해집니다. 내가 쓴 함수가 몇 번 도는지를 항상 따지세요.

둘째, 반복 횟수가 줄어드니 복잡도도 낮아졌다고 착각합니다. 위 ④번 패턴처럼 안쪽 반복이 절반만 돌아도 여전히 O(n²)입니다. 상수 배는 빅오에서 사라집니다. 절반으로 줄이는 것과 매번 절반씩 잘라 내는 것(로그)은 완전히 다릅니다.

셋째, 문자열 연결을 반복문 안에서 합니다. 파이썬 문자열은 수정할 수 없어서, s += "x"를 반복하면 매번 새 문자열을 만듭니다. n번 반복하면 O(n²)이 될 수 있습니다. 조각을 리스트에 모았다가 "".join(리스트)로 한 번에 합치는 편이 안전합니다.

넷째, 변수 이름 n에만 집착합니다. 입력이 두 종류라면 복잡도도 두 문자로 씁니다. 예를 들어 크기 n인 배열과 크기 m인 배열을 겹쳐 돈다면 O(n × m)이지 O(n²)이 아닙니다. 문제에 변수가 몇 개인지 먼저 확인하세요.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	순차는 더하고, 중첩은 곱한다
2	매번 절반으로 줄면 O(log n)
3	코딩 테스트는 최악을 기준으로 판단한다
4	`append`는 상각 O(1) — 가끔 O(n)이 섞인다
5	내장 함수도 복잡도가 있다
6	입력 범위로 목표 복잡도를 역산한다

지금 해 볼 것은 최근에 푼 문제의 코드를 열어 복잡도를 세어 보는 것입니다. 반복문이 몇 겹인지, 그 안에 O(n) 연산이 숨어 있지 않은지 확인해 보세요.

다음 3강 「배열과 리스트」부터는 자료구조로 들어갑니다. 파이썬 리스트가 내부적으로 어떻게 동작하기에 인덱스 접근은 빠르고 중간 삽입은 느린지, 그리고 리스트를 다룰 때 시간 초과를 부르는 패턴을 정리하겠습니다.

빅오 표기 자세히