이 편에서 만드는 파일

이 편은 이론 편이라 coding-test/에 새 폴더를 만들지 않습니다. 대신 03편부터 모든 문제 풀이에 적용할 복잡도 주석 규칙을 이 편에서 정합니다.

개념 정리

Big-O 표기법이란

Big-O(빅오)는 입력 크기 n이 커질 때 실행 시간(또는 메모리)이 늘어나는 정도만 표현하는 표기법입니다. 상수 배와 낮은 차수 항은 무시하고, 가장 크게 영향을 주는 항만 남깁니다. 예를 들어 실제 연산 횟수가 3n + 5여도 n이 아주 커지면 +5와 계수 3은 상대적으로 무의미해지므로 O(n)으로 표기합니다.

자주 등장하는 차수

n이 10에서 1000으로 100배 늘어날 때 O(n)은 100배만 늘어나지만 O(n^2)는 10000배로 늘어납니다. 코딩테스트에서 시간 제한을 지키려면 문제의 입력 크기를 보고 어떤 차수까지 허용되는지 먼저 가늠해야 합니다. 예를 들어 n이 100000 규모면 O(n^2)는 대개 시간 초과이고 O(n log n) 이하가 필요합니다.

시간·공간 트레이드오프

같은 문제를 시간을 더 쓰고 공간을 아끼거나, 공간을 더 쓰고 시간을 아끼는 두 방향으로 풀 수 있습니다. “배열에 중복된 값이 있는지 확인”하는 문제로 비교합니다.

04편에서 Map과 Set으로 조회를 O(1)에 가깝게 만드는 이유가 바로 이 트레이드오프입니다. 메모리가 넉넉한 코딩테스트 환경에서는 대체로 시간을 아끼는 쪽을 선택합니다.

문제 유형 → 자료구조 선택 지도

이 표는 문제를 처음 읽었을 때 “어떤 자료구조로 접근할지” 판단하는 출발점입니다. 실제로는 여러 자료구조를 함께 쓰는 문제도 많습니다.

복잡도 주석 규칙(03편부터 모든 solution.js에 적용)

앞으로 모든 solution.js는 파일 경로 주석 다음 줄에 시간·공간 복잡도를 이유와 함께 적습니다.

// coding-test/03-arrays-and-strings/01-example/solution.js
// 시간복잡도: O(n) — 배열을 한 번 순회하며 합을 구한다
// 공간복잡도: O(1) — 입력 외 추가 메모리를 쓰지 않는다
export function solution(nums) {
  // ...
}

시간복잡도와 공간복잡도 뒤에는 항상 표기법과 그 근거를 한 문장으로 씁니다. 근거 없이 표기법만 적으면 나중에 왜 그 복잡도인지 스스로도 설명하기 어려워집니다.

실습

터미널에서 복잡도 차이를 직접 체감합니다. 이 실험은 coding-test/ 저장소에 저장하지 않고 임시로 실행만 합니다.

node -e "const n = 20000000; console.time('linear'); let sum = 0; for (let i = 0; i < n; i++) { sum += i; } console.timeEnd('linear');"

node -e "const n = 4000; console.time('quadratic'); let count = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { count++; } } console.timeEnd('quadratic');"

확인

• O(n) 코드는 n을 2배로 늘려도 실행 시간이 대략 2배 정도로만 늘어납니다.
• O(n^2) 코드는 n을 2배로 늘리면 실행 시간이 대략 4배로 늘어납니다(반복 횟수가 n * n이므로).
• 두 결과를 비교해 “차수가 높을수록 입력이 커질 때 훨씬 불리해진다”는 것을 실행 시간으로 확인합니다.

직접 해보기

1. O(n log n)에 해당하는 코드로 Array.prototype.sort()를 큰 배열에 적용해보고, n을 2배로 늘렸을 때 실행 시간이 O(n)보다는 많이, O(n^2)보다는 적게 늘어나는지 확인해봅니다.
2. 문제 유형 → 자료구조 선택 지도 표를 보지 않고, “값이 중복 없이 존재하는지 빠르게 확인하는 문제”에 어떤 자료구조가 적합할지 먼저 답해본 뒤 표와 비교해봅니다.

자주 하는 실수

확인 문제

참고 자료

• MIT OpenCourseWare - 6.006 Introduction to Algorithms 
• Node.js Docs - console.time