알고리즘을 처음 배울 때 반복문 하나가 O(n)이고 그 안에 반복문이 하나 더 있으면 O(n²)이라고 계산하는 방법을 배운다.
여러 주문의 상품을 확인하는 코드를 생각해보자.
for (const order of orders) {
for (const item of order.items) {
prepareShipment(item);
}
}겉으로 보면 반복문이 두 겹이다.
입문 단계에서는 중첩 반복문의 비용이 곱해질 수 있다는 사실을 이해하는 데 유용한 예제다.
하지만 이 코드를 바로 O(n²)이라고 부를 수는 없다.
n은 주문 수인가, 주문 상품 수인가?- 각 주문에 항상 주문 수만큼의 상품이 들어 있는가?
- 안쪽 반복문이 같은 상품을 매번 다시 확인하는가?
- 모든 주문의 상품 수를 합하면 실제로 몇 개인가?
- 서로 다른 두 목록을 비교하는가?
- 안쪽 반복문의 위치가 매번 처음으로 돌아가는가?
- 일정한 개수만 확인하고 중단하는가?
- 반복문 안에서 데이터베이스나 외부 API를 호출하는가?
- 결과로 만들어야 하는 데이터 자체가 얼마나 큰가?
코드의 들여쓰기만 보면 실행 횟수를 잘못 판단할 수 있다.
실제 서비스에서 반복문의 복잡도는 반복문이 몇 겹으로 보이는지가 아니라, 입력 데이터가 처리 과정 전체에서 실제로 몇 번 방문되고 어떤 작업을 반복하는지 계산해 판단해야 한다.
주문 수와 상품 수를 같은 n으로 부르면 비용을 잘못 계산한다
크리스가 주문한 상품들을 물류센터의 출고 작업으로 변환한다고 생각해보자.
function createShipmentTasks(orders) {
const tasks = [];
for (const order of orders) {
for (const item of order.items) {
tasks.push({
orderId: order.id,
productId: item.productId,
quantity: item.quantity,
});
}
}
return tasks;
}바깥 반복문은 주문을 확인한다.
안쪽 반복문은 현재 주문에 포함된 상품만 확인한다.
주문 수를 n이라고 해보자. 각 주문의 상품 수도 항상 n개라면 실행 횟수는 n × n이므로 O(n²)이다.
하지만 실제 주문은 각기 다른 상품 수를 가진다.
주문 A: 상품 2개
주문 B: 상품 1개
주문 C: 상품 4개안쪽 반복문의 전체 실행 횟수는 다음과 같다.
2 + 1 + 4 = 7주문 3개마다 전체 상품 7개를 다시 확인하는 것이 아니다.
각 상품을 자신의 주문 안에서 한 번씩만 확인한다.
전체 주문 수를 n, 모든 주문에 포함된 상품 수의 합을 m이라고 하면 처리 비용을 다음처럼 표현할 수 있다.
O(n + m)바깥 반복문의 주문 확인과 안쪽 반복문의 전체 상품 확인을 합친 것이다.
상품이 없는 주문도 존재할 수 있으므로 주문 자체를 확인하는 비용과 상품을 확인하는 비용을 구분하는 편이 정확하다.
중첩 반복문이라는 코드 모양보다 각 데이터가 전체 실행 동안 몇 번 처리되는지가 중요하다.
안쪽 반복문이 매번 같은 전체 목록을 확인하면 비용은 곱해진다
모든 주문 상품에 적용 가능한 배송 규칙을 찾는다고 생각해보자.
function findShippingRules(
orderItems,
shippingRules
) {
const results = [];
for (const item of orderItems) {
for (const rule of shippingRules) {
if (rule.appliesTo(item)) {
results.push({
item,
rule,
});
}
}
}
return results;
}각 상품마다 모든 배송 규칙을 처음부터 다시 확인한다.
상품 수를 n, 배송 규칙 수를 m이라고 하면 실행 횟수는 다음과 같다.
n × m따라서 시간 복잡도는 O(nm)이다.
상품 수와 배송 규칙 수가 우연히 모두 같은 크기 n으로 증가한다면 O(n²)이라고 단순화할 수 있다.
하지만 실제 서비스에서는 두 데이터가 다르게 증가할 수 있다.
- 주문 상품은 최대 100개다.
- 배송 규칙은 최대 10개로 고정되어 있다.
- 상품은 계속 증가하지만 배송 규칙은 거의 변하지 않는다.
- 국가별 정책이 늘어나면서 배송 규칙도 증가할 수 있다.
배송 규칙이 항상 최대 10개라면 상품 수가 증가해도 안쪽 반복은 최대 10번이다.
O(n × 10) → O(n)Big O에서는 고정된 상수를 생략하므로 주요 증가 방식은 O(n)이다.
다만 규칙 하나를 확인하는 실제 비용이 크다면 10번의 반복도 무시할 수 없다.
복잡도 분석에서는 증가 방식을 보고, 실제 성능 판단에서는 작업 한 번의 비용도 측정해야 한다.
반복 횟수가 삼각형처럼 줄어들어도 O(n²)일 수 있다
같은 주문에 중복 상품이 있는지 모든 상품 쌍을 비교한다고 생각해보자.
function findDuplicatePairs(items) {
const duplicates = [];
for (
let first = 0;
first < items.length;
first += 1
) {
for (
let second = first + 1;
second < items.length;
second += 1
) {
if (
items[first].productId ===
items[second].productId
) {
duplicates.push([
items[first],
items[second],
]);
}
}
}
return duplicates;
}안쪽 반복문은 항상 n번 실행되지 않는다.
- 첫 번째 상품은 나머지
n - 1개와 비교한다. - 두 번째 상품은 나머지
n - 2개와 비교한다. - 마지막 상품은 비교할 대상이 없다.
전체 비교 횟수는 다음과 같다.
(n - 1) + (n - 2) + ... + 1
= n(n - 1) / 2약 n² / 2에 비례하므로 Big O에서는 O(n²)이다.
안쪽 반복문이 점점 짧아진다는 사실만으로 선형 시간이 되는 것은 아니다.
전체 실행 횟수를 모두 더했을 때 어떤 항이 증가를 주도하는지 확인해야 한다.
이 경우에는 각 상품이 많은 다른 상품과 비교되므로 데이터가 커질수록 비교 횟수가 빠르게 늘어난다.
중복 검사를 위한 모든 쌍 비교는 저장 구조로 줄일 수 있다
중복 상품 ID만 찾는 것이 목적이라면 모든 상품 쌍을 비교할 필요가 없다.
이미 본 상품 ID를 저장할 수 있다.
function findDuplicateProductIds(items) {
const seen = new Set();
const duplicates = new Set();
for (const item of items) {
if (seen.has(item.productId)) {
duplicates.add(item.productId);
} else {
seen.add(item.productId);
}
}
return [...duplicates];
}각 상품을 한 번 확인한다.
Set의 평균적인 조회와 삽입이 빠르게 처리된다고 보면 전체 탐색은 평균 O(n)에 가깝다.
대신 상품 ID를 저장하기 위한 추가 메모리가 필요하다.
두 구현은 출력 의미도 다를 수 있다.
| 필요한 결과 | 적절할 수 있는 방법 |
|---|---|
| 중복된 상품 ID 목록 | Set으로 한 번 탐색 |
| 중복된 모든 상품 쌍 | 모든 쌍을 만들어야 할 수 있음 |
| 상품별 중복 개수 | Map에 개수 저장 |
| 데이터베이스의 중복 행 | 그룹 집계나 고유 제약 사용 |
| 중복 삽입 자체를 방지 | 데이터베이스 고유 제약 사용 |
알고리즘을 바꾸기 전에 출력이 무엇인지 확인해야 한다.
중복 여부만 필요하다면 O(n²) 비교는 불필요할 수 있다. 그러나 모든 중복 쌍을 결과로 반환해야 하고 결과 자체가 매우 크다면 그 결과를 만드는 비용도 피할 수 없다.
안쪽 위치가 처음으로 돌아가지 않으면 전체 실행은 선형일 수 있다
두 물류센터에서 생성된 출고 이벤트를 시간순으로 합친다고 생각해보자.
두 이벤트 목록은 이미 시간순으로 정렬되어 있다.
function mergeShipmentEvents(
warehouseEvents,
carrierEvents
) {
const merged = [];
let warehouseIndex = 0;
let carrierIndex = 0;
while (
warehouseIndex <
warehouseEvents.length &&
carrierIndex <
carrierEvents.length
) {
if (
warehouseEvents[warehouseIndex]
.occurredAt <=
carrierEvents[carrierIndex]
.occurredAt
) {
merged.push(
warehouseEvents[warehouseIndex]
);
warehouseIndex += 1;
} else {
merged.push(
carrierEvents[carrierIndex]
);
carrierIndex += 1;
}
}
while (
warehouseIndex <
warehouseEvents.length
) {
merged.push(
warehouseEvents[warehouseIndex]
);
warehouseIndex += 1;
}
while (
carrierIndex <
carrierEvents.length
) {
merged.push(
carrierEvents[carrierIndex]
);
carrierIndex += 1;
}
return merged;
}코드에는 여러 while 반복문이 있다.
첫 번째 반복문에서는 두 목록을 함께 확인하므로 중첩된 비교처럼 느낄 수도 있다.
그러나 각 반복에서 두 인덱스 중 하나는 반드시 증가한다.
한 이벤트를 확인한 뒤 그 위치로 다시 돌아가지 않는다.
물류센터 이벤트 수를 n, 배송사 이벤트 수를 m이라고 하면 각 이벤트는 최대 한 번 결과에 추가된다.
따라서 전체 비용은 다음과 같다.
O(n + m)반복문이 여러 개라는 사실보다 각 인덱스가 처음부터 끝까지 몇 번 이동하는지가 중요하다.
중첩되어 보여도 포인터가 전체에서 한 번만 이동할 수 있다
주문 상품이 창고 구역순으로 정렬되어 있고, 같은 구역의 상품을 하나의 출고 묶음으로 만들고 싶다고 생각해보자.
function groupItemsByZone(items) {
const groups = [];
let start = 0;
while (start < items.length) {
let end = start;
while (
end < items.length &&
items[end].zoneId ===
items[start].zoneId
) {
end += 1;
}
groups.push(
items.slice(start, end)
);
start = end;
}
return groups;
}바깥 while 안에 다시 while이 있으므로 겉으로는 O(n²)처럼 보일 수 있다.
하지만 안쪽의 end는 현재 구역의 마지막 상품까지 이동한다. 바깥 반복이 끝날 때 start는 바로 그 end 위치로 이동한다.
이미 확인한 상품을 다시 처음부터 탐색하지 않는다.
예를 들어 상품이 100개라면 안쪽 반복문들의 전체 실행 횟수도 약 100번이다.
첫 번째 그룹에서 20개 확인
두 번째 그룹에서 30개 확인
세 번째 그룹에서 50개 확인
전체 확인: 20 + 30 + 50 = 100따라서 그룹 경계를 찾는 반복 자체는 O(n)이다.
다만 slice가 각 그룹의 상품을 새로운 배열로 복사한다면 복사 비용도 포함해야 한다. 모든 상품이 결과 배열에 한 번씩 복사되므로 전체 복사 비용 역시 O(n)이다.
중첩 반복문의 복잡도를 판단할 때는 다음을 확인해야 한다.
- 안쪽 인덱스가 바깥 반복마다 0으로 돌아가는가?
- 이미 처리한 데이터를 다시 방문하는가?
- 각 데이터가 전체 실행 동안 최대 몇 번 처리되는가?
반복문 안에서 값을 제거해도 전체 처리 횟수는 제한될 수 있다
출고 대기열에서 이미 취소된 주문을 앞에서 제거한다고 생각해보자.
function processQueue(queue) {
while (queue.length > 0) {
while (
queue.length > 0 &&
queue[0].status === "CANCELLED"
) {
queue.shift();
}
if (queue.length === 0) {
break;
}
ship(queue.shift());
}
}반복문이 두 겹이지만 하나의 주문이 여러 번 제거되지는 않는다.
각 주문은 다음 중 하나의 방식으로 큐에서 한 번 빠진다.
- 취소된 주문으로 제거된다.
- 정상 주문으로 출고 처리된다.
따라서 논리적인 처리 횟수는 주문 수에 비례한다.
그러나 JavaScript 배열의 shift()는 첫 번째 요소를 제거한 뒤 나머지 요소의 위치를 옮길 수 있다. 이 구현 세부사항 때문에 실제 비용은 커질 수 있다.
인덱스를 이동시키는 방식이 더 적절하다.
function processQueue(queue) {
let index = 0;
while (index < queue.length) {
if (
queue[index].status !==
"CANCELLED"
) {
ship(queue[index]);
}
index += 1;
}
}각 주문을 한 번 확인하고 배열 요소를 계속 이동시키지 않는다.
알고리즘의 논리적인 방문 횟수뿐 아니라 사용하는 자료구조의 연산 비용도 확인해야 한다.
break가 있다고 무조건 빠른 것은 아니다
상품 바코드를 찾다가 일치하면 반복을 멈출 수 있다.
function findItem(items, barcode) {
for (const item of items) {
if (item.barcode === barcode) {
return item;
}
}
return null;
}첫 번째 상품이 일치하면 한 번만 확인한다.
하지만 상품이 없거나 마지막에 있다면 모든 상품을 확인해야 한다.
따라서 최악의 경우 시간 복잡도는 O(n)이다.
중첩 반복문에도 break가 있을 수 있다.
function hasRestrictedCombination(
items
) {
for (const first of items) {
for (const second of items) {
if (
isRestrictedPair(first, second)
) {
return true;
}
}
}
return false;
}금지된 조합을 일찍 발견하면 빠르게 끝날 수 있다.
그러나 금지된 조합이 없다면 모든 쌍을 확인한다.
최악의 경우는 여전히 O(n²)이다.
실제 서비스에서는 평균적으로 빨리 종료되는지와 최악의 경우 얼마나 오래 걸리는지를 구분해야 한다.
break가 있다는 코드 모양만으로 복잡도를 낮춰서는 안 된다.
안쪽 반복이 고정된 횟수라면 O(n²)이 아니다
물류 작업자가 상품 하나를 스캔할 때 최대 세 개의 바코드 형식을 확인한다고 생각해보자.
const barcodeFormats = [
readEan13,
readUpc,
readInternalCode,
];
for (const item of items) {
for (const readBarcode of barcodeFormats) {
const result = readBarcode(item.image);
if (result) {
item.barcode = result;
break;
}
}
}바깥 반복은 상품 수 n에 따라 증가한다.
안쪽 반복은 최대 세 번만 실행한다.
O(n × 3) → O(n)barcodeFormats가 앞으로도 최대 세 개로 유지되는 고정된 규칙이라면 선형 증가로 볼 수 있다.
하지만 플러그인 방식으로 바코드 판독 규칙을 계속 추가할 수 있다면 안쪽 목록도 입력이 된다.
상품 수를 n, 판독 규칙 수를 m이라고 하면 O(nm)으로 표현해야 한다.
어떤 값이 정말 고정되어 있는지 확인하지 않고 상수로 취급해서는 안 된다.
현재 3개라는 사실과 서비스가 최대 3개만 허용한다는 정책은 다르다.
반복문 안의 데이터베이스 호출은 실행 횟수보다 더 큰 문제를 만든다
출고 대상 주문을 확인하면서 각 주문의 상품을 별도로 조회할 수 있다.
for (const order of orders) {
const items =
await orderItemRepository.findByOrderId(
order.id
);
for (const item of items) {
prepareShipment(item);
}
}메모리에서 상품을 처리하는 횟수는 전체 상품 수에 비례한다.
하지만 주문마다 데이터베이스 조회가 한 번씩 발생한다.
주문이 n개라면 다음 비용이 생긴다.
주문 조회 1번
+ 상품 조회 n번
+ 전체 상품 처리복잡도를 단순화하면 조회 횟수는 O(n)이다.
그러나 데이터베이스 왕복 한 번은 메모리 비교 한 번보다 훨씬 비쌀 수 있다.
필요한 주문 상품을 한 번에 조회할 수 있다.
const orderIds = orders.map(
(order) => order.id
);
const items =
await orderItemRepository.findByOrderIds(
orderIds
);
const itemsByOrderId = new Map();
for (const item of items) {
const orderItems =
itemsByOrderId.get(item.orderId) ?? [];
orderItems.push(item);
itemsByOrderId.set(
item.orderId,
orderItems
);
}이 코드는 필요한 상품을 묶어서 조회하고 주문 ID별로 분류한다.
이후 각 주문은 메모리의 Map에서 자신의 상품 목록을 찾을 수 있다.
데이터베이스 왕복 횟수는 줄지만 한 번에 조회하는 데이터 양은 커진다. 주문 수가 매우 많다면 안전한 크기로 나누거나 저장소에서 바로 처리하는 방법을 검토해야 한다.
중첩 반복문의 실행 횟수만 세면 네트워크와 데이터베이스 비용을 놓칠 수 있다.
데이터의 위치에 따라 같은 반복도 다른 설계가 된다
모든 출고 기록을 서버로 가져온 뒤 오늘 처리할 기록만 찾는 코드를 생각해보자.
const allShipments =
await shipmentRepository.findAll();
const todaysShipments =
allShipments.filter(
(shipment) =>
shipment.createdAt >= todayStart
);배열 필터링은 전체 출고 기록 수에 대해 O(n)이다.
하지만 문제는 반복문보다 전체 데이터를 저장소에서 읽고 전송하는 과정에 있다.
필요한 범위를 데이터베이스에서 먼저 제한해야 한다.
SELECT
id,
order_id,
status,
created_at
FROM shipments
WHERE warehouse_id = $1
AND created_at >= $2
ORDER BY created_at ASC;적절한 인덱스가 있다면 저장소가 전체 기록을 확인하지 않고 관련 범위를 찾을 수 있다.
CREATE INDEX shipments_warehouse_created_idx
ON shipments (
warehouse_id,
created_at
);애플리케이션 반복문을 분석하기 전에 어떤 데이터가 메모리에 들어오는지 확인해야 한다.
처리 대상이 저장소에서 이미 줄어들 수 있다면 서버에서 전체 데이터를 반복할 이유가 없다.
외부 입력이 반복 횟수를 결정한다면 상한을 검증해야 한다
물류 관리 API가 한 번에 처리할 주문 수를 입력받는다고 생각해보자.
const batchSize = Number(
request.body.batchSize
);
const orders =
await orderRepository.findReadyOrders({
warehouseId,
limit: batchSize,
});정상적인 관리 화면은 50이나 100을 보낼 수 있다.
하지만 검증되지 않은 외부 사용자가 매우 큰 값을 전달하면 서버가 거대한 주문과 상품 목록을 처리할 수 있다.
if (
!Number.isInteger(batchSize) ||
batchSize < 1 ||
batchSize > 500
) {
throw new Error(
"한 번에 처리할 주문 수는 1개 이상 500개 이하여야 한다."
);
}이 코드는 서비스가 지원하기로 한 배치 크기만 허용한다.
외부 입력의 상한을 정하면 다음 비용도 제한할 수 있다.
- 한 번에 조회할 주문 수
- 함께 가져올 주문 상품 수
- 서버 메모리에 생성할 객체 수
- 출고 작업 생성 횟수
- 응답 본문 크기
- 트랜잭션이 유지되는 시간
복잡도를 알고 있어도 입력 크기가 무제한이면 요청 하나의 최대 비용을 예측하기 어렵다.
입력 검증은 형식 안전성뿐 아니라 성능과 서비스 보호를 위한 경계다.
계산 결과와 저장된 출고 상태를 구분해야 한다
중첩 반복문으로 출고 작업을 계산했다고 생각해보자.
const shipmentTasks =
createShipmentTasks(orders);이 결과는 조회한 주문과 상품을 기준으로 만든 계산 데이터다.
작업을 계산한 뒤 실제 저장하기 전까지 주문이 취소되거나 다른 작업자가 먼저 출고를 시작할 수 있다.
따라서 계산 결과를 바로 확정된 상태로 믿어서는 안 된다.
const result =
await shipmentRepository.claimIfReady({
orderId: task.orderId,
warehouseId,
claimedBy: workerId,
claimedAt: serverNow,
});저장소는 현재 주문이 여전히 출고 준비 상태인지 확인하면서 상태를 변경해야 한다.
UPDATE orders
SET
fulfillment_status = 'PROCESSING',
claimed_by = $3,
claimed_at = $4
WHERE id = $1
AND warehouse_id = $2
AND fulfillment_status = 'READY'
RETURNING id, fulfillment_status;이 쿼리는 변경 순간에도 주문이 READY일 때만 성공한다.
서버가 만든 출고 작업 목록은 후보 데이터다. 주문의 최종 출고 상태에 대한 Source of Truth는 데이터베이스다.
반복문을 더 빠르게 만드는 일과 공유된 상태를 정확하게 변경하는 일은 서로 다른 책임이다.
결과 자체가 크다면 알고리즘도 그만큼의 비용을 부담한다
모든 주문 상품 쌍의 호환성을 반환하라는 요구사항이 있다고 생각해보자.
상품이 n개일 때 가능한 쌍의 수는 약 n² / 2다.
결과 자체가 O(n²) 크기라면 모든 결과를 실제로 만들어 반환하는 알고리즘이 O(n)으로 끝날 수는 없다.
function createAllItemPairs(items) {
const pairs = [];
for (
let first = 0;
first < items.length;
first += 1
) {
for (
let second = first + 1;
second < items.length;
second += 1
) {
pairs.push([
items[first],
items[second],
]);
}
}
return pairs;
}이 코드는 가능한 모든 쌍을 결과에 포함한다.
문제는 알고리즘이 비효율적이라는 데만 있지 않다. 요구한 출력 자체가 매우 크다.
이때는 요구사항을 다시 확인해야 한다.
- 모든 쌍이 정말 필요한가?
- 문제가 있는 쌍만 반환하면 되는가?
- 하나라도 문제가 있는지만 알면 되는가?
- 첫 번째 충돌을 찾으면 멈춰도 되는가?
- 결과를 페이지 단위로 생성할 수 있는가?
- 데이터베이스 제약으로 잘못된 조합 생성을 막을 수 있는가?
출력의 크기를 줄이지 않고 처리 시간만 크게 줄일 수는 없는 경우가 있다.
복잡도 분석은 구현뿐 아니라 요구사항의 비용도 드러낸다.
실제 실행 횟수를 기록하면 가정을 확인할 수 있다
코드만 보고 예상한 실행 횟수가 실제 데이터에서도 맞는지 측정할 수 있다.
let orderVisits = 0;
let itemVisits = 0;
for (const order of orders) {
orderVisits += 1;
for (const item of order.items) {
itemVisits += 1;
prepareShipment(item);
}
}
logger.info("Shipment iteration count", {
orderCount: orders.length,
orderVisits,
itemVisits,
});이 코드는 주문과 상품이 실제로 몇 번 처리되었는지 기록한다.
데이터베이스 조회 횟수도 함께 관찰할 수 있다.
logger.info("Shipment batch metrics", {
orderCount: orders.length,
itemCount: items.length,
queryCount,
elapsedMs,
});다음 값을 함께 보면 병목을 더 정확히 이해할 수 있다.
- 주문 수
- 전체 주문 상품 수
- 주문당 상품 수의 분포
- 반복문 실행 횟수
- 데이터베이스 쿼리 수
- 처리 시간
- 생성된 출고 작업 수
- 실패하거나 건너뛴 주문 수
복잡도 분석은 증가 구조를 예상한다.
측정은 실제 데이터가 그 예상과 어떻게 만나는지 확인한다.
중첩 반복문의 비용을 판단할 때 물어봐야 할 질문
중첩된 반복문을 발견했을 때 다음 질문을 확인할 수 있다.
- 각 반복문이 어떤 현실의 데이터를 순회하는가?
- 바깥 목록과 안쪽 목록의 크기를 같은
n으로 불러도 되는가? - 주문 수, 전체 상품 수와 주문당 상품 수를 구분했는가?
- 안쪽 반복문은 바깥 반복마다 전체 목록을 처음부터 다시 확인하는가?
- 각 데이터는 실행 전체에서 최대 몇 번 방문되는가?
- 안쪽 인덱스가 매번 초기화되는가, 계속 앞으로만 이동하는가?
- 여러 반복문의 전체 실행 횟수를 합하면 얼마인가?
- 삼각형처럼 줄어드는 반복 횟수의 합을 계산했는가?
- 안쪽 반복 횟수는 실제로 고정된 상수인가?
- 현재 작다는 이유만으로 증가 가능한 입력을 상수로 취급하고 있지는 않은가?
break가 없는 경우나 가장 늦게 종료되는 경우도 확인했는가?- 중복 탐색을
Set이나Map으로 줄일 수 있는가? - 추가 자료구조에 필요한 메모리와 갱신 비용은 얼마인가?
- 모든 쌍을 비교해야 하는 비즈니스 이유가 있는가?
- 출력 자체가
O(n²)크기인지 확인했는가? - 전체 결과 대신 일부 결과나 존재 여부만 필요한가?
- 반복문 안에서 데이터베이스나 외부 API를 호출하는가?
- 메모리 연산과 네트워크 왕복을 같은 비용으로 보고 있지는 않은가?
- 반복 조회를 하나의 묶음 조회로 바꿀 수 있는가?
- 묶음 요청의 최대 크기를 안전하게 제한했는가?
- 필요한 데이터를 저장소에서 먼저 줄일 수 있는가?
- 조회 조건에 맞는 인덱스가 있는가?
- 외부 입력이 반복 횟수를 무제한으로 늘릴 수 있는가?
- 계산된 후보와 저장된 원본 상태를 구분했는가?
- 최종 상태 변경은 최신 데이터를 기준으로 처리하는가?
- 동시에 여러 작업자가 같은 주문을 처리하지 않도록 보장하는가?
- 실제 반복 횟수와 쿼리 수를 운영 지표로 측정했는가?
- 평균 데이터뿐 아니라 가장 큰 주문과 배치도 확인했는가?
- 현재 병목이 반복 횟수인지, 작업 한 번의 비용인지 구분했는가?
- 코드 모양이 아니라 실행 횟수를 자연어로 설명할 수 있는가?
이 질문은 중첩 반복문을 모두 제거하기 위한 목록이 아니다.
입력 크기가 작고 모든 쌍 비교가 실제 요구사항이라면 중첩 반복문이 가장 명확한 구현일 수 있다. 중요한 것은 데이터가 증가할 때 몇 번 실행되는지 알고 선택하는 것이다.
복잡도는 들여쓰기가 아니라 데이터의 움직임으로 판단한다
중첩 반복문은 비용이 빠르게 증가할 가능성을 알려주는 신호다.
하지만 반복문이 두 겹이라는 사실만으로 O(n²)이라고 결론 내릴 수는 없다.
다음 경우는 서로 다르다.
- 각 주문의 상품을 한 번씩 처리하면
O(n + m)일 수 있다. - 상품마다 모든 배송 규칙을 확인하면
O(nm)이다. - 모든 상품 쌍을 비교하면
O(n²)이다. - 두 정렬된 목록의 인덱스가 앞으로만 움직이면
O(n + m)일 수 있다. - 안쪽 반복이 최대 세 번으로 고정되어 있다면
O(n)이다. - 반복문 안에서 원격 조회를 실행하면 같은 복잡도라도 실제 비용이 커질 수 있다.
- 출력 자체가 모든 쌍이라면 결과 크기 때문에
O(n²)비용이 필요할 수 있다.
따라서 코드를 분석할 때는 반복문 개수를 세는 데서 멈추면 안 된다.
- 각 입력의 의미와 크기를 정의한다.
- 인덱스가 언제 초기화되고 어디까지 이동하는지 확인한다.
- 각 데이터가 전체 실행 동안 몇 번 방문되는지 센다.
- 여러 반복의 횟수를 곱해야 하는지 더해야 하는지 판단한다.
- 안쪽 작업의 실제 비용을 확인한다.
- 저장소와 네트워크를 오가는 횟수를 별도로 계산한다.
- 필요한 출력의 크기와 정확성 조건을 함께 본다.
- 실제 데이터에서 방문 횟수와 처리 시간을 측정한다.
실제 서비스에서 중첩 반복문의 복잡도는 들여쓰기의 깊이로 결정되지 않는다. 입력 데이터가 처리 과정 전체에서 얼마나 자주 다시 방문되고, 각 방문에서 어떤 저장소와 계산을 사용하는지 추적하여 판단해야 한다.
중첩 반복문을 보자마자 두려워할 필요는 없다.
대신 각 반복문이 현실의 어떤 데이터를 움직이며 이미 처리한 데이터를 다시 확인하는지 살펴봐야 한다. 이 과정을 거치면 단순한 선형 처리와 실제 제곱 비용을 구분하고, 필요한 곳에만 자료구조와 조회 방식을 개선할 수 있다.
다음 글에서는 평균적인 요청이 빠르다는 사실만으로 좋은 알고리즘이라고 판단할 수 없는 이유와 최악의 입력이 장애와 타임아웃으로 이어지는 과정을 살펴본다.
