서론: 데이터가 100억 개라면?
제가 NASA에서 은하 데이터를 분석할 때 겪은 일입니다. 별 1,000개를 분석하는 코드를 짰더니 0.1초 만에 결과가 나왔습니다. "완벽해!"라고 생각하고 100억 개의 전체 은하 데이터를 넣었더니, 컴퓨터가 멈춰버렸습니다. 계산해 보니 그 코드로 결과를 보려면 3만 년이 걸린다는 결론이 나왔습니다.
코딩에서 '효율성'이란 단순히 지금 빠르냐가 아닙니다. "데이터가 무한대로 늘어날 때, 처리 시간은 얼마나 늘어나는가?"에 대한 수학적 예측입니다.
오늘 16편에서는 개발자 면접의 단골 질문이자, 좋은 코드의 기준이 되는 'Big-O(빅오) 표기법'에 대해 아주 쉽게 풀어보겠습니다.
본론 1: O(1) vs O(n), 순간 이동과 도보 여행
알고리즘의 성능을 나타내는 Big-O 표기법은 '최악의 시나리오'를 가정합니다.
1. O(1) - 상수 시간 (Constant Time)
데이터가 1개든 100억 개든 똑같이 한 번에 끝나는, 꿈의 속도입니다.
예: "배열의 3번째 칸에 있는 값을 가져와라." (배열 크기가 아무리 커도 주소 계산 한 번이면 끝납니다.)
2. O(n) - 선형 시간 (Linear Time)
데이터가 10배 늘어나면 시간도 정직하게 10배 늘어납니다.
예: "도서관의 모든 책을 처음부터 끝까지 뒤져서 특정 책을 찾아라." (운이 나쁘면 맨 마지막 책일 수 있으므로 다 뒤져야 합니다.)
본론 2: O(n²)의 저주 (이중 반복문)
초보자가 가장 많이 저지르는 실수가 바로 O(n²) 알고리즘을 짜는 것입니다.
보통 반복문(for) 안에 또 반복문(for)을 넣을 때 발생합니다. 데이터가 10배 늘어나면 시간은 100배(10의 제곱) 늘어납니다.
데이터가 1만 개만 되어도 1억 번을 계산해야 하므로, NASA의 대용량 데이터를 처리할 때는 절대 사용해서는 안 되는 비효율적인 방식입니다.
본론 3: O(log n), 우주를 반으로 접는 마법
그렇다면 NASA는 그 많은 별을 어떻게 검색할까요? 바로 O(log n), 로그 시간 알고리즘을 사용합니다. 대표적인 예가 '이진 탐색(Binary Search)'입니다.
업다운(Up-Down) 게임을 생각해보세요. 1부터 100까지 숫자 중 하나를 맞힐 때, "1이니? 2니?"(O(n))라고 묻는 바보는 없습니다. "50!"을 외쳐서 범위를 절반으로 뚝 자르죠.
- 놀라운 효율: 데이터가 40억 개라도, 딱 32번만 반으로 자르면(2의 32승) 원하는 데이터를 무조건 찾을 수 있습니다.
- 이것이 바로 구글 검색이나 데이터베이스가 순식간에 결과를 보여주는 비결입니다.
결론: 컴퓨터를 혹사시키지 말라
좋은 개발자는 컴퓨터 성능을 믿고 막무가내로 코드를 짜지 않습니다. 대신 더 똑똑한 방법(알고리즘)을 고민하여 컴퓨터가 일하는 횟수를 획기적으로 줄여줍니다.
여러분의 코드는 O(1)입니까, 아니면 O(n²)입니까? 이 질문에 답할 수 있다면 여러분은 이미 아마추어의 단계를 넘어선 것입니다.
다음 [Part 17. 임베디드 시스템: 보이지 않는 컴퓨터들] 편에서는, 화려한 서버나 PC가 아닌, 냉장고부터 화성 탐사선까지 우리 주변 사물 속에 숨어 있는 초소형 컴퓨터의 세계를 탐험해 보겠습니다.