3강 / 20강

알고리즘의 비용 — 주문 100건과 100만 건은 다르다

잘 돌아가던 코드가 세일 날 서버를 멈추는 이유

개발자가 만든 상품 검색 기능이 있습니다. 테스트할 때는 0.01초. 완벽합니다. 그런데 오픈 6개월 뒤, 상품이 3만 개가 되자 5초가 걸립니다. 서버를 두 배 좋은 걸로 바꿨더니 2.5초. 여전히 느립니다.

무엇이 잘못된 걸까요? 서버가 부족한 게 아닙니다. 알고리즘이 잘못 골라진 것입니다.

고등학생잘 돌아가던 코드가 세일 날 멈추는 이유

부제가 실제로 자주 일어나는 일입니다.

평소엔 멀쩡한데 손님이 몰리면 서버가 죽는다

왜 그런가

알고리즘의 비용이 데이터 양에 따라 달라지기 때문입니다. 그리고 어떻게 달라지는지가 알고리즘마다 달라요.

이름	데이터가 2배면	느낌
O(1)	그대로	몇 개든 상관없다
O(log n)	1 늘어난다	거의 안 는다
O(n)	2배	정직하다
O(n²)	4배	위험

O(n²) 는 데이터가 10배 되면 시간이 100배

그래서 세일 날 죽습니다

평소 주문 1,000건에 0.5초 걸리던 코드가 있다고 합시다. 세일 날 주문이 10배로 늘면?

0.5초 × 100 = 50초

50초 동안 응답이 없으면 손님이 떠납니다. 그리고 요청이 계속 쌓여 서버가 완전히 멈춥니다.

비유 — 계단 오르기

건물	층수 2배면
엘리베이터 (O(1))	거의 같다
계단 (O(n))	2배 힘들다
매 층 청소하며 (O(n²))	4배

평소엔 계단도 괜찮다 — 100층이 되면 다르다

고등학생이것은 실화에 가깝습니다

note 가 실화에 가까운 이야기라고 합니다. 실제로 이런 사고가 계속 일어나요.

전형적인 시나리오

서비스를 작게 시작한다 — 상품 100개
이중 반복으로 짜도 잘 돌아간다 (1만 번은 순식간)
서비스가 커진다 — 상품 10,000개
같은 코드가 1억 번 돌게 된다
서버가 멈춘다

코드는 안 바뀌었는데 세상이 바뀌었다

이게 무서운 이유

테스트에서는 안 잡힙니다. 개발할 때는 데이터가 적으니까요.

환경	데이터	결과
개발자 컴퓨터	100개	0.01초 — 문제없다
실제 서비스	100,000개	17분

작게 시험하면 큰 문제가 안 보인다

비유 — 좁은 길

동네에 좁은 길이 있습니다. 차가 몇 대일 땐 괜찮아요. 그런데 아파트가 들어서면? 매일 막힙니다.

길은 그대로인데 차가 늘어난 거죠.

지금 괜찮다고 계속 괜찮지 않다

그래서 미리 봅니다

"데이터가 10배가 되면 어떻게 되나" 를 코드를 짤 때 미리 물어보는 겁니다.

그게 O 표기가 있는 이유예요 — 커질 때 어떻게 되는지만 보는 도구입니다.

비용을 재는 자 — 걸음 수

알고리즘의 비용은 초(second)로 재지 않습니다. 초는 컴퓨터 성능·네트워크·그날 서버 상태에 따라 매번 다르니까요.

대신 "데이터가 n개일 때 몇 걸음을 걷는가"를 셉니다. 이 걸음 수를 n에 대한 식으로 쓴 것이 시간 복잡도예요.

같은 1,000개 데이터인데 걸음 수가 1 vs 1,000 vs 500,000.

Python 브라우저에서 실행

n = 1000   # 상품 개수

# ① 상수 — n과 상관없이 항상 1걸음
def 첫상품(상품들):
    return 상품들[0]

# ② 선형 — 전부 한 번씩 훑는다 → n걸음
def 총재고(상품들):
    합 = 0
    for s in 상품들:
        합 += s
    return 합

# ③ 제곱 — 모든 쌍을 비교한다 → n×n 걸음
def 중복찾기(상품들):
    쌍 = 0
    for i in range(len(상품들)):
        for j in range(i + 1, len(상품들)):
            쌍 += 1
    return 쌍

상품들 = list(range(n))
print("① 상수  : 1 걸음")
print("② 선형  :", n, "걸음")
print("③ 제곱  :", 중복찾기(상품들), "걸음  ← n이 1000인데 벌써 50만 걸음")

O(빅오) 표기법 — 큰 그림만 남기기

걸음 수가 3n + 7 이든 5n + 100 이든, n이 100만이 되면 +7이나 +100은 아무 의미가 없습니다. 그래서 자잘한 것은 다 버리고 가장 크게 자라는 항만 남깁니다. 이 표기법이 O( ), "빅오"예요.

표기	이름	쇼핑몰에서의 예	n=100만일 때
`O(1)`	상수	주문번호로 딱 하나 조회 (해시)	1번
`O(log n)`	로그	정렬된 목록에서 이진 탐색	20번
`O(n)`	선형	전체 매출 합산	100만 번
`O(n log n)`	선형로그	상품 목록 정렬	2,000만 번
`O(n²)`	제곱	모든 상품 쌍을 비교	1조 번 💀

맨 아래를 보세요. 1조 번입니다. 1초에 1억 번을 계산하는 컴퓨터라도 약 3시간이 걸립니다. 이래서 O(n²)은 실무에서 "터진다"고 말해요.

고등학생숫자로 외우지 말고 이렇게 기억하세요

note 가 좋은 조언을 합니다. O 표기를 외우지 말고 감각으로 기억하라고요.

"데이터가 2배가 되면 시간이 몇 배?"

표기	2배면	어떤 코드
O(1)	그대로	딕셔너리 조회 (8강)
O(log n)	+1 걸음	이진 탐색 (5강)
O(n)	2배	반복문 한 겹
O(n log n)	2배 조금 넘게	정렬 (6강)
O(n²)	4배	반복문 두 겹

반복문이 몇 겹인지만 세도 대략 안다

가장 쉬운 판별법

반복문이 없다 → O(1)
한 겹 → O(n)
두 겹 → O(n²)
절반씩 줄여 간다 → O(log n)

코드를 보고 겹 수를 세는 습관

그런데 O 표기가 무시하는 것

O(n) 이라고 해서 정확히 n 번은 아닙니다. 2n 도, 100n 도 전부 O(n) 이에요.

O 표기는 커질 때의 모양만 본다

왜 그래도 되냐면 — n 이 커지면 100n 보다 n² 이 훨씬 커지거든요.

n	100n	n²
10	1,000	100
1,000	10만	100만

작을 때는 상수가 중요하고, 커지면 모양이 이긴다

🎮 성장 곡선 실험실

말로만 들으면 감이 안 옵니다. 직접 재 봅시다. 아래 위젯은 여러분의 브라우저에서 실제로 코드를 돌려 시간을 측정합니다. n을 2배씩 키우면서 시간이 몇 배로 늘어나는지 확인해 보세요.

고등학생O(n²) 를 알아보는 법

note 가 실전 요령을 줍니다. 코드에서 O(n²) 를 눈으로 찾는 법이요.

반복문 안에 반복문이 있으면 의심하라

그런데 숨어 있을 수 있습니다

겉보기	실제
`for x in A:` `if x in B:`	B 가 리스트면 안에서 또 훑는다 → O(n²)
같은 코드	B 가 집합이면 즉시 확인 → O(n)

in 한 글자가 O(n) 일 수도 O(1) 일 수도 있다

9강에서 이 이야기를 제대로 합니다. 지금은 "in 도 비용이 있다" 만 기억하세요.

다른 숨은 O(n²)

코드	왜 느린가
`list.pop(0)` 반복	앞에서 빼면 전부 밀린다 (11강)
문자열을 `+` 로 이어 붙이기	매번 새로 만든다
`list.remove()` 반복	찾느라 훑는다

한 줄짜리 코드에도 안에서 반복이 돌 수 있다

그럼 어떻게 확인하나

20강의 답이 나옵니다 —

추측하지 말고 측정하라

데이터를 2배로 늘려 돌려 보세요. 시간이 4배가 되면 O(n²) 입니다.

이건 코드를 안 읽어도 알 수 있는 방법이에요. 남이 만든 라이브러리에도 쓸 수 있습니다.

최선 · 최악 · 평균

같은 알고리즘도 운에 따라 다릅니다. 창고 100칸을 앞에서부터 뒤지는 알고리즘을 생각해 보세요.

최선 — 찾는 물건이 1번 칸에 있음 → 1걸음
최악 — 마지막 칸에 있거나, 아예 없음 → 100걸음
평균 — 대체로 절반쯤 → 50걸음

실무에서 기준으로 삼는 것은 거의 항상 최악입니다. "평균 0.1초"인 서비스라도 최악이 30초면 그 손님은 떠나니까요.

직접 측정해 보세요. n이 2배면 시간은 4배 — 그것이 O(n²)의 정체입니다.

Python 브라우저에서 실행

import time

def 느린방법(n):        # O(n²)
    c = 0
    for i in range(n):
        for j in range(n):
            c += 1
    return c

for n in (200, 400, 800, 1600):
    t0 = time.time()
    느린방법(n)
    t = time.time() - t0
    print(f"n = {n:>5}   시간 {t*1000:>8.1f} ms")

print()
print("n이 2배가 될 때마다 시간이 대략 4배씩 늘어나는지 확인해 보세요.")

🤔 확인 문제

상품 1,000개에서 0.5초 걸리던 O(n²) 알고리즘이 있습니다. 상품이 10,000개가 되면 대략 얼마나 걸릴까요?

🤔 확인 문제

다음 중 데이터가 100만 개일 때 가장 빠른 것은?

🤔 확인 문제

시스템 관리자가 성능을 판단할 때 보통 기준으로 삼는 것은?