20강 / 20강

알고리즘 고르기 — 느릴 때 무엇을 먼저 볼까

측정 · 병목 · 처방, 그리고 전 19강의 정리

드디어 마지막 강입니다. 지금까지 배운 것을 현장에서 쓰는 순서로 정리해 봅시다.

"사이트가 느려요"라는 신고를 받았습니다. 무엇부터 해야 할까요?

고등학생느릴 때 무엇을 먼저 볼까

20강은 실전 매뉴얼입니다. "느려요" 라는 신고를 받았을 때 하는 일이요.

순서 — 측정 → 병목 → 처방

왜 이 순서인가

단계	안 하면
측정	엉뚱한 데를 고친다
병목 찾기	1%를 고치고 만족한다
처방	—

고치기 전에 어디가 느린지 부터

비유 — 아플 때

배가 아픕니다. 아무 약이나 먹나요?

아니죠. 어디가 왜 아픈지 먼저 봅니다. 그다음 약을 정해요.

진단 없이 처방하면 낫지 않는다

그런데 사람들은 자꾸 건너뜁니다

"여기가 느릴 것 같아" 하고 바로 고칩니다. 그리고 대개 틀립니다.

짐작	실제
"반복문이 느릴 거야"	DB 조회가 90% 였다
"계산이 무거워"	로그 쓰기가 느렸다

병목은 거의 항상 예상 밖에 있다

고등학생추측하지 말고 측정하라

note 의 제목이 이 강의의 철칙입니다.

머리로 짐작한 병목은 대개 틀린다

왜 틀리나

사람은 코드 길이로 무게를 짐작합니다. 그런데 실제 비용은 다른 데 있어요.

코드	보기	실제
복잡한 계산 20줄	무거워 보인다	0.001초
`db.query(...)` 1줄	가벼워 보인다	0.1초

한 줄이 100배 무거울 수 있다

특히 무거운 것들

무엇	왜
네트워크 (DB · API)	다른 컴퓨터에 다녀온다
디스크	메모리보다 수천 배 느리다
반복문 안의 위 두 가지	최악

반복문 안에서 DB 를 부르는 것 — N+1 문제

측정하는 법

시간을 찍는다 — 단계마다 time.time()
프로파일러 — 어느 함수가 얼마나 썼는지 자동으로
로그 — 19강의 그것

숫자가 나오면 논쟁이 끝난다

"이게 느릴 거야" 는 의견이고 "이게 전체의 87% 를 씁니다" 는 사실이에요.

어디를 고칠지 잘못 고르면 노력이 통째로 낭비됩니다.

Python 브라우저에서 실행

# 암달의 법칙 — 전체의 5%를 차지하는 부분을 100배 빠르게 만들면?
전체 = 100.0

for 비중, 배속 in [(0.05, 100), (0.30, 2), (0.80, 2), (0.80, 10)]:
    남는부분 = 전체 * (1 - 비중)
    고친부분 = 전체 * 비중 / 배속
    새시간 = 남는부분 + 고친부분
    print(f"전체의 {비중*100:>4.0f}% 를 {배속:>3}배 빠르게 → "
          f"총 시간 {새시간:>5.1f} ({전체/새시간:.2f}배 개선)")

print()
print("💡 5%를 100배 빠르게 해봐야 전체는 1.05배. 80%를 2배 하는 게 훨씬 낫습니다.")
print("   → '가장 큰 조각'을 찾는 것이 최적화의 90%입니다.")

느릴 때 확인하는 순서

#	확인	발견되면	관련 강
1	어느 요청이 느린가 (p95·p99 로그)	범위를 좁힌다	19강
2	DB 쿼리가 몇 번 나가는가	N+1 문제 → 딕셔너리로 합치기	8강
3	조회 컬럼에 인덱스가 있는가	Full Scan O(n) → 인덱스 O(log n)	5강
4	같은 계산을 반복하는가	캐시 · 메모이제이션	13·16강
5	이중 반복문이 있는가	O(n²) → 해시나 정렬로 낮추기	3·6·8강
6	전부 정렬하고 앞 몇 개만 쓰는가	힙 Top-N	10강
7	대기열이 계속 쌓이는가	처리기 증설 · 유입 제한	11·17강

위에서부터 순서대로 보세요. 대부분 3번 안에 답이 나옵니다.

자료·연산별 도구 요약표

하고 싶은 일	도구	비용	강
열쇠 하나로 정확히 찾기	딕셔너리 · 집합	`O(1)`	8
정렬된 데이터에서 찾기	이진 탐색 · DB 인덱스	`O(log n)`	5
조건이 복잡한 검색	선형 탐색 · 검색 엔진	`O(n)`	4
순서대로 나열	`sorted(key=…)`	`O(n log n)`	6·7
합계 · 평균 · 개수	한 번 훑기 · Counter	`O(n)`	10
상위 N개만	`heapq.nlargest`	`O(n log k)`	10
명단 겹치기 · 빼기	집합 연산	`O(n+m)`	9
순서대로 처리	`deque`	`O(1)`	11
급한 것 먼저 처리	`heapq` 우선순위 큐	`O(log n)`	11
빠른 근사 최적	탐욕	`O(n log n)`	12
정확한 최적	동적 계획법	`O(n·m)`	13
N단계 이내 연결 찾기	BFS	`O(V+E)`	15
최소 비용 경로	다익스트라	`O(E log V)`	15
같은 계산 반복 줄이기	LRU 캐시	`O(1)`	16
과부하 막기	토큰 버킷	`O(1)`	17
이상 징후 찾기	규칙 점수 · Z-점수	`O(n)`	18

정답은 상황에 따라 다릅니다. 그 '상황'을 판단하는 법이 이 강의의 결론이에요.

Python 브라우저에서 실행

# 같은 문제를 네 가지로 풀어 시간을 비교합니다
# 문제: 주문 5만 건에서 특정 상품코드의 주문을 모두 찾기
import time, random, bisect
from collections import defaultdict

random.seed(1)
N = 50000
주문 = [(f"P{random.randint(0, 999):03d}", i) for i in range(N)]
찾을코드 = "P042"

# ① 선형 탐색 — 매번 전부 훑기
t0 = time.time()
결과1 = [o for o in 주문 if o[0] == 찾을코드]
t1 = time.time() - t0

# ② 정렬 + 이진 탐색
t0 = time.time()
정렬 = sorted(주문)
코드들 = [o[0] for o in 정렬]
lo = bisect.bisect_left(코드들, 찾을코드)
hi = bisect.bisect_right(코드들, 찾을코드)
결과2 = 정렬[lo:hi]
t2 = time.time() - t0

# ③ 딕셔너리 인덱스 (한 번 만들고 여러 번 조회)
t0 = time.time()
색인 = defaultdict(list)
for o in 주문:
    색인[o[0]].append(o)
t_build = time.time() - t0
t0 = time.time()
결과3 = 색인[찾을코드]
t3 = time.time() - t0

print(f"① 선형 탐색          {t1*1000:>8.2f} ms   ({len(결과1)}건)")
print(f"② 정렬+이진탐색      {t2*1000:>8.2f} ms   ({len(결과2)}건)")
print(f"③ 딕셔너리 색인 구축 {t_build*1000:>8.2f} ms")
print(f"   딕셔너리 조회      {t3*1000:>8.4f} ms   ({len(결과3)}건)  ← 두 번째부터 사실상 공짜")
print()
print("💡 한 번만 찾으면 ①이 이깁니다. 여러 번 찾으면 ③이 압도적이에요.")
print("   '몇 번 쓸 것인가'가 알고리즘 선택의 결정적 기준입니다.")

고등학생성급한 최적화를 조심하세요

note 가 반대 방향의 경고를 합니다. 빠르게 만드는 것도 지나치면 해 라고요.

필요 없는 최적화는 코드만 어렵게 만든다

왜 해로운가

대가	설명
읽기 어렵다	남이 (그리고 미래의 내가) 못 읽는다
버그가 는다	복잡할수록 틀린다
시간을 쓴다	다른 일을 못 한다

10ms 를 5ms 로 줄이려고 하루를 쓰는 것

그럼 언제 최적화하나

느리다는 것을 확인했을 때
어디가 느린지 측정했을 때
그 부분이 전체의 큰 몫일 때

전체의 1% 를 두 배 빠르게 해 봐야 0.5% 다

비유 — 등굣길 줄이기

등교에 50분 걸립니다. 어디를 줄일까요?

구간	시간	절반으로 줄이면
집 → 정류장	3분	1.5분 절약
버스	40분	20분 절약

큰 것부터 — 작은 것을 아무리 줄여도 티가 안 난다

그리고 균형

그렇다고 아무렇게나 짜라는 건 아닙니다.

이건 처음부터	이건 나중에
자료구조 고르기 (리스트냐 집합이냐)	미세한 코드 다듬기
반복 겹 수 줄이기	상수 배 줄이기

구조는 처음에, 세부는 나중에

서버를 키우는 것과 알고리즘을 고치는 것

	서버 증설	알고리즘 개선
효과	대개 2~4배	때로 1,000배 이상
비용	매달 계속 나감	한 번 고치면 끝
데이터가 10배 되면	또 증설해야 함	O(log n)이면 거의 그대로
적합한 경우	이미 효율적인데 양이 많을 때	복잡도가 잘못 골라졌을 때

O(n²)를 서버로 해결하려는 것이 가장 흔하고 가장 비싼 실수입니다. 데이터가 10배가 되면 100배 느려지는데, 서버를 100대로 늘릴 수는 없으니까요.

고등학생20강을 한 장으로

여기까지 오신 것을 축하합니다. 🎉 주문 한 건의 순서에서 시작해 여기까지 왔어요.

배운 도구를 한 표로

문제	도구	강
찾기	선형 · 이진 · 해시	4·5·8
줄 세우기	정렬 · 다중 기준	6·7
겹치고 빼기	집합	9
세고 순위	Counter · Top-K	10·19
순서대로 처리	큐 · 우선순위 큐	11
최선 고르기	탐욕 · DP	12·13
관계 다루기	그래프 · BFS/DFS	14·15
빠르게	캐시	16
지키기	속도 제한 · 이상 탐지	17·18

그런데 진짜 남는 것은 도구가 아닙니다

배운 것은 비용을 생각하는 습관이다

이 코드는 데이터가 10배가 되면 어떻게 되나 (3강)
반복문이 몇 겹인가 (3강)
담는 그릇이 맞나 — 리스트냐 집합이냐 (9강)
같은 계산을 되풀이하고 있지 않나 (13·16강)
측정했나, 짐작인가 (20강)

다섯 가지 물음이면 대부분의 성능 문제가 보인다

그리고 맞바꿈

이 강의에서 몇 번이나 나온 구조 —

얻는 것	내주는 것
속도	공간 (캐시 · 인덱스 · DP)
속도	정확도 (탐욕 · 근사)
안전	편의 (속도 제한 · 이상 탐지)

공짜는 없다 — 무엇을 내줄지 고르는 것이 설계다

이제 대학생 눈높이로 한 번 더 읽어 보세요 — 코드가 훨씬 잘 읽힐 겁니다.

🤔 확인 문제

전체 실행 시간의 5%를 차지하는 부분을 100배 빠르게 만들면 전체는?

🤔 확인 문제

데이터가 10배 늘 때마다 서버를 증설하는 것으로 해결되지 않는 경우는?

🤔 확인 문제

알고리즘을 고를 때 가장 먼저 생각해야 할 것은?