상품 목록에서 사용자가 고른 상품만 강조하는 화면이 있다. 코드는 한 줄이다.
const visible = products.filter(p => selectedIds.includes(p.id))상품 100개로 개발할 때는 아무 문제가 없었다. 그런데 운영 데이터로 상품 2만 개, 선택 1만 개가 되자 화면이 눈에 띄게 멈칫한다. 코드 어디에도 이중 루프가 없는데 왜 그럴까?
이 책은 이런 장면에서 출발한다. 장마다 실무 코드에 숨은 패턴 하나에 이름을 붙이고, 입력을 바꿔 가며 일이 어떻게 늘어나는지 그림으로 보거나, 코드를 한 줄씩 실행해 보며 변수가 어떻게 바뀌는지 따라간다. 예제는 TypeScript와 Python 두 가지로 적었다. 코드 위의 언어 버튼으로 바꾸면 책 전체의 예제가 고른 언어로 보인다. 장 끝에는 조금 어려운 보너스 문제가 있다. 힌트를 하나씩 열어 가며 풀어 보자. 개념 정의는 Big-O 표기법(빅오) 노트에 있다. 로그·합 공식·경우의 수 같은 수학이 낯설면 『개발 수학』에서 그 부분만 먼저 읽고 와도 된다.
읽는 법 몇 가지. 예측 문제는 모르면 찍어도 된다. 틀린 답과 그 뒤의 해설이 맞힌 답보다 오래 남는다. 답과 진행 기록은 이 브라우저에만 저장되고 누구에게도 보이지 않는다. 시간 제한은 없고, 장은 순서대로 읽지 않아도 된다. O(n log n) 같은 표기가 나오면 바로 옆에 말로 읽는 법과 숫자 예가 있으니, 기호만 보고 멈추지 말고 그 다음 문장까지 읽는다.
includes 안에 숨은 루프
Array.prototype.includes는 배열을 앞에서부터 한 칸씩 보며 찾는 값과 같은지 비교한다. 명세에 적힌 알고리즘도 인덱스 0부터 길이만큼 도는 반복문이다(ECMAScript 명세). Python의 x in 리스트도 같다. 리스트에서 값을 찾는 비용은 리스트 길이에 비례한다(Python Wiki: TimeComplexity).
그러니 filter 안의 includes는 겉보기엔 한 줄이어도 실제로는 루프 안의 루프다.
상품 1,000개, 고른 id 1,000개다. 고른 id 중 상품 목록에 있는 것은 하나도 없다. products.filter(p => selectedIds.includes(p.id))는 비교를 몇 번 할까?
선택지와 해설 보기
실험 includes 안에 숨은 루프
행이 상품 id, 열이 고른 id입니다. 상품 하나마다 고른 목록을 왼쪽부터 비교합니다. 비교한 칸은 노랑(≠), 찾은 칸은 초록(=), 찾은 뒤 보지 않은 칸은 회색(–)입니다.
| 상품＼고름 | 5 | 3 | |
|---|---|---|---|
| 3 | |||
| 8 | |||
| 5 |
- 해볼 것
- 상품 3개 입력을 끝까지 돌려 비교가 몇 번인지 본다
- '하나도 없음' 입력으로 바꿔 끝까지 돌려 본다
상품 3개 입력을 끝까지 돌리면 비교한 칸이 5개 켜진다. 3은 둘째 칸에서, 5는 첫째 칸에서 찾았고, 찾으면 그 줄의 나머지 칸은 보지 않는다. 8은 고른 목록에 없어서 두 칸을 모두 비교했다. '하나도 없음' 입력은 격자 16칸이 전부 켜진다.
includes는 찾으면 그 자리에서 멈추니, 찾는 값이 없을수록, 있어도 뒤쪽에 있을수록 비교가 늘어난다. 최악은 상품마다 고른 목록 전체를 훑는 경우이고, 그때 비교 횟수는 (상품 수) × (고른 수)다. 예측의 상품 1,000개, 고른 id 1,000개면 1,000 × 1,000 = 100만 번이다.
Big-O: 자라는 모양만 본다
비교 횟수를 정확히 세는 것보다 중요한 질문이 있다. 입력이 커질 때 이 수가 어떤 모양으로 자라나? 는 이 모양만 남긴다. 상품과 고른 id가 둘 다 n개라면 최악의 비교 횟수는 n × n이고, O(n²)라고 적는다. 상수 배(2n이든 3n이든)와 작은 항(n² + n의 n)은 n이 커질수록 전체에서 차지하는 몫이 작아져서 버린다(n = 1,000이면 n²은 100만, n은 1,000이라 전체의 0.1%).
| 표기 | 이름 | n이 10배가 되면 | 실무에서 자주 보는 모양 |
|---|---|---|---|
O(1) | 상수 | 그대로 | Set.has, Map.get(평균), 배열 인덱스 접근 |
O(log n) | 로그 | 조금 늘어남 | 정렬된 배열에서 이분 탐색(binary search, 6장) |
O(n) | 선형 | 10배 | 배열 한 번 훑기, includes, indexOf |
O(n log n) | 선형 로그 | 10배보다 조금 더 | 비교 정렬(sort) |
O(n²) | 제곱 | 100배 | 루프 안의 includes·find·filter |
표의 log n은 n을 2로 몇 번 나누면 1이 되는지 센 수다. n = 1,000이면 약 10, 100만이면 약 20이다(『개발 수학』 Unit 2).
마지막 줄이 이 장의 주인공이다. 제곱은 n이 작을 때는 티가 나지 않다가 어느 순간 갑자기 느려진다. 테스트 데이터로는 멀쩡하던 화면이 운영 데이터에서만 멈추는 이유다.
Set으로 바꾸기: 한 번씩만 묻는다
고른 id를 Set에 한 번 담아 두면, 상품마다 "이 id가 있나?"를 앞에서부터 훑지 않고 바로 묻는다. ECMAScript 명세는 Set을 해시 테이블(hash table)이나 그와 비슷하게 평균적으로 원소 수보다 느리게 자라는(sublinear) 시간에 찾는 방식으로 구현하라고 요구한다(ECMAScript 명세). Python의 set도 x in s가 평균 O(1)이다(Python Wiki: TimeComplexity). 어떻게 한 번에 찾는지는 다음 장에서 본다.
const selected = new Set(selectedIds) // 고른 수만큼 한 번const visible = products.filter(p => selected.has(p.id)) // 상품마다 한 번
실험 Set으로 바꾸면 한 번씩만 묻는다
같은 입력을 Set으로 풀었습니다. 고른 id를 Set에 한 번 담고, 상품마다 "있나?"를 한 번만 묻습니다.
- 6
- 1
- 7
- 2
- ×4
- ×9
- ✓2
- ✓7
- ✓1
- ✓6
- 해볼 것
- 세 입력을 모두 눌러, Set은 늘 '고른 수 + 상품 수'번인데 includes는 찾는 위치에 따라 입력마다 달라지는 것을 본다
Set을 만드는 데 고른 수만큼, 찾는 데 상품 수만큼 일한다. 전체는 n + n = O(n)이다. 메모리를 n만큼 더 써서 시간을 산 셈이다. 이렇게 시간과 메모리를 맞바꾸는 일은 이 책 내내 나온다.
n이 커지면 얼마나 차이 날까
실험 n이 커지면 비교 횟수는 어떻게 자랄까
상품 n개, 고른 id n개일 때 최악의 비교 횟수입니다. 비교 한 번에 1나노초가 걸린다고 치고 걸리는 시간도 함께 적었습니다.
includes는 약 10마이크로초, Set은 약 200나노초 걸립니다.
- 해볼 것
- n을 1,000으로 놓고 두 방식의 비교 횟수를 견줘 본다
- n을 100,000까지 올려 본다
n이 1,000일 때 제곱 방식은 비교 100만 번이다. 비교 한 번에 1나노초(1초 = 10억 나노초)라고 치면 1밀리초라서 아직 느낌이 없다. 10만이 되면 100억 번, 약 10초다. 같은 n에서 Set 방식은 20만 번, 0.2밀리초다. 실제 시간은 기기와 엔진에 따라 다르다. 하지만 n이 10배 늘 때 시간이 10배 느는 코드와 100배 느는 코드의 차이는 어느 기기에서나 그대로다.
반대로 n이 작다고 확신할 수 있으면 includes도 괜찮다. 원소 5개짜리 배열을 굳이 Set으로 바꾸면 만드는 비용과 메모리만 늘고 읽기는 어려워진다. 는 "n이 커질 수 있나?"를 먼저 묻게 하는 도구다. 빠르기를 판정하는 것은 측정이다.
실무 코드에서 찾아보기
제곱은 눈에 띄는 이중 루프 모양으로 나타나지 않는다. 대개 배열 메서드 한 줄 안에 숨어 있다.
함정 찾기 AI가 짠 주문 요약 함수, 데이터가 늘면 어디가 느려질까?
“사용자별 주문 합계와 이름 목록을 만들고, 주문 id를 차례로 로그로 남기는 함수를 짜 줘.”
의심스러운 줄을 모두 눌러 표시한 뒤 “검토 끝”을 누르세요. 함정은 3개입니다.
정리하면 n²은 map 안의 filter(O(U × O)), reduce 안의 스프레드 복사(약 n²/2번), shift()로 큐 비우기에 숨어 있다. 각각 Map으로 묶기, map, for…of로 바꾸면 O(n)이다.
확인 문제 장을 덮기 전에 떠올려 보기
1. users.map(u => orders.find(o => o.userId === u.id))의 시간 복잡도(time complexity)는? (사용자 U명, 주문 O건, 최악의 경우)
2. Set으로 바꿔 O(n²)을 O(n)으로 줄일 때 대신 늘어나는 것은?
3. 원소가 늘 5개 이하인 배열에서 includes를 쓰는 코드는?
더 풀어 보기(선택) · push는 왜 평균 O(1)일까
꽉 차면 두 배 크기의 새 공간을 만들고 원소를 모두 옮겨 담는 동적 배열(dynamic array)이 있다. 용량 1인 빈 배열에서 push를 n번 하면 원소 복사는 모두 몇 번 일어날까? n이 2의 거듭제곱(1, 2, 4, 8처럼 2를 거듭 곱한 수)일 때 식으로 구하고, 거듭제곱이 아닌 n(예시의 9)도 직접 세어 보자. 이 결과로 push 한 번의 평균 비용이 O(1)인 이유를 설명해 보자.
n = 8 → 복사 ?번 n = 9 → 복사 ?번