실전 코드를 빅오 표현법으로 표현하기
크리스가 동료 개발자가 작성한 코드를 리뷰하고 있다.
변수 이름도 깔끔하고 주석도 잘 달려있다. 그런데 반복문 구조가 어딘가 묘하다.
"이 함수, 데이터가 100개일 땐 괜찮은데 10,000개가 넘어가면 서버가 멈출 것 같은데요?"
"어? 반복문 하나밖에 안 썼는데 왜요?"
동료의 반문에 크리스는 정확한 근거를 들어 설명해야 했다.
"이건 반복문이 하나처럼 보이지만, 사실 숨겨진 반복문이 있어서 O(N^2)이에요!"
오늘은 막연했던 빅오(Big-O) 개념을 실제 코드에 대입해 계산해 보는 실전 훈련 시간이다. 덧셈과 곱셈만 할 줄 알면 누구나 할 수 있다
1. 빅오 계산의 4가지 법칙
복잡한 수학 공식은 필요 없다. 코드를 눈으로 훑으며 아래 4가지 규칙만 적용하면 된다.
규칙 1: 최악을 생각하라 (Worst Case)
"운 좋게 바로 찾았다"는 없다. 항상 "찾는 데이터가 배열의 맨 마지막에 있다"고 가정한다.
규칙 2: 상수는 버려라 (Drop Constants)
규칙 3: 덜 중요한 항은 무시하라 (Drop Non-Dominants)
규칙 4: 단계별 연산 합산
2. 실전 예제 분석
예제 1: 덧셈 (상수 무시)
function printCount(n) {
for (let i = 0; i < n; i++) { // n번 반복
console.log(i);
}
for (let j = 0; j < n; j++) { // n번 반복
console.log(j);
}
}예제 2: 곱셈 (중첩 반복)
function printPairs(n) {
for (let i = 0; i < n; i++) { // n번 반복
for (let j = 0; j < n; j++) { // 안에서 또 n번 반복
console.log(i, j);
}
}
}예제 3: 입력이 다를 때 (N vs M)
function processItems(arr1, arr2) {
arr1.forEach(item => console.log(item)); // a번 반복
arr2.forEach(item => console.log(item)); // b번 반복
}3. 크리스의 지적: 숨겨진 복잡도 찾기
이제 크리스가 지적했던 동료의 코드를 보자. 반복문은 분명 하나다.
// ⚠️ 함정 카드 발동
function findCommon(arr1, arr2) {
// arr1을 순회 (N번)
arr1.forEach(item1 => {
// arr2에 item1이 있는지 확인 (includes)
if (arr2.includes(item1)) {
console.log("찾았다:", item1);
}
});
}왜 이 코드가 O(N^2)일까?
범인은 includes() 메서드다.
우리가 1편에서 배웠듯, 자바스크립트의 includes, indexOf, slice 등은 내부적으로 배열을 처음부터 끝까지 뒤지는 반복문(O(N))이다.
즉, 이 코드는 for 문 안에 for 문이 들어있는 것과 똑같다.
해결책:
arr2를 Set(해시 테이블)이나 객체로 바꾸면 검색을 O(1)로 줄일 수 있다. 그러면 전체 복잡도는 O(N)으로 내려간다. 이것이 알고리즘 최적화의 기본 패턴이다.
4. 1장을 마치며: 알고리즘적 사고 장착 완료
지금까지 우리는 알고리즘의 기초 체력을 다졌다.
이제 크리스는 코드를 짤 때 단순히 "돌아가게" 만드는 것에 만족하지 않는다.
"이 데이터가 100만 개라면?"이라는 질문을 던지고, 시간과 공간 효율성을 따져가며 더 나은 로직을 고민하는 엔지니어가 되었다.
다음 장부터는 본격적인 무기들을 수집할 차례다.
데이터를 순서대로 나열하는 것만으로도 검색 속도를 획기적으로 높일 수 있다. 개발자 면접의 단골 손님, 정렬(Sorting) 알고리즘의 세계로 떠나보자.
정렬 알고리즘이란 편에서 계속된다.