앱이 느린 이유를 추측하지 마세요: 실용적인 Big O Notation 가이드

Source: Dev.to

왜 Big O가 중요한가

코딩을 시작할 때 주된 목표는 보통 동작하게 만드는 것뿐입니다. 기능이 배포되고 버그가 해결되면 우리는 만족합니다. 하지만 사용자 수가 늘어나고 데이터 양이 커지면, 배열을 순회하는 간단한 작업조차 브라우저를 멈추게 할 수 있습니다.

Big O는 입력 크기가 커짐에 따라 코드 성능이 어떻게 확장되는지를 이야기하는 방법입니다. 즉, 입력이 10배 커지면 내 앱은 얼마나 느려지는가? 라는 질문에 답합니다.

---

공간‑시간 트레이드오프

대부분의 경우 알고리즘을 더 빠르게 만들기(시간 복잡도 개선) 위해서는 임시 데이터를 저장할 메모리(공간 복잡도)를 더 많이 사용해야 합니다. 예를 들어 조회 테이블을 만드는 경우가 그렇습니다. RAM이 제한된 기기(예: 오래된 스마트폰)에서는 메모리 부족으로 인한 크래시를 피하기 위해 의도적으로 느린 알고리즘을 선택하기도 합니다. 최적화는 언제나 상황에 맞춰야 합니다.

---

이차 vs. 선형: Set 활용

트럭 번호판을 추적하는 Yard Management System (YMS)이 있다고 가정해 봅시다. 다음과 같은 데이터가 있습니다:

• arriving – 새로 도착한 트럭의 번호판
• registered – 데이터베이스에 이미 저장된 번호판

도착한 트럭 중 이미 등록된 트럭을 찾아야 합니다.

완전 탐색 (O(n²))

function findRegisteredTrucks(arriving: string[], registered: string[]): string[] {
  const matches: string[] = [];

  for (let i = 0; i = {};

Set을 이용한 최적화 (O(n))

function findRegisteredTrucksOptimized(arriving: string[], registered: string[]): string[] {
  const registeredSet = new Set(registered);
  return arriving.filter(plate => registeredSet.has(plate));
}

정렬은 단순 순회보다 본질적으로 복잡하지만, 비교 기반 정렬의 최적 표준 속도는 O(n log n)입니다.

---

정리

• 루프를 주의하라 – 큰 데이터셋에 중첩 루프를 피하세요.
• Set과 Map을 활용하라 – O(1) 조회를 위해 사용합니다.
• 결과를 캐시하라 (메모이제이션) – 반복 계산이 있을 때 유용합니다.
• 공간‑시간 트레이드오프를 기억하라: 더 빠른 알고리즘은 보통 더 많은 메모리를 필요로 합니다.

당신이 해결한 최악의 성능 병목 현상은 무엇이었나요? 댓글로 이야기를 공유해 주세요! 👇