Ch.1 빅오와 복잡도 분석
로그의 마법 — O(log n)과 이진탐색
사전에서 단어를 어떻게 찾나요?
10만 단어가 담긴 영어 사전에서 'python'을 찾아야 합니다. 첫 페이지부터 한 장씩 넘기면 5만 페이지를 봐야 할 수도 있지만, 가운데를 펼치면 17번이면 충분합니다.
왜 반씩 나누면 그렇게 빨라질까?
매번 반을 버리면 남는 양이 기하급수적으로 줄어듭니다. 이것이 log n의 비밀입니다.
핵심 개념
O(log n)
매번 탐색 범위를 반으로 줄이는 알고리즘의 시간 복잡도
이진탐색
정렬된 배열에서 중간값과 비교하며 범위를 반씩 줄이는 탐색법
핵심 내용
업다운 게임을 해봅시다. 1~100 중 숫자를 맞추세요
50! → '업' → 75! → '다운' → 63! ... 매번 범위가 절반으로 줄어듭니다
100 → 50 → 25 → 13 → 7 → 4 → 2 → 1 7번이면 1~100 중 어떤 숫자든 찾습니다 이것이 바로 log₂(100) ≈ 7
n이 2배가 되어도 log n은 1만 증가합니다
10억 개 데이터에서 30번이면 답을 찾습니다. 이것이 log의 힘!
이진탐색을 Python으로 구현해봅시다
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1arr = [1, 3, 5, 7, 9, 11]에서 7을 찾는 과정을 추적합니다
6개 원소에서 3번만에 찾았습니다. log₂(6) ≈ 2.6 → 올림하면 3!
이진탐색에는 반드시 지켜야 할 조건이 있습니다
이진탐색 전제 조건: 1. 배열이 정렬되어 있어야 한다 2. 인덱스로 접근 가능해야 한다 (연결 리스트는 불가) 3. 정렬 비용: O(n log n) — 한 번 정렬 후 여러 번 탐색하면 이득
면접 팁: '정렬되어 있나요?'라고 먼저 물어보세요. 이 한마디가 점수입니다
10억 개의 정렬된 데이터에서 이진탐색으로 찾는 데 최대 몇 번 비교?
이진탐색을 사용하려면 배열이 반드시 정렬되어 있어야 한다
이진탐색의 시간 복잡도를 채우세요: O(___)
이진탐색의 시간 복잡도: O(___)
로그의 마법사
핵심 용어
O(log n)
매번 탐색 범위를 반으로 줄이는 시간 복잡도
이진탐색
정렬된 배열에서 중간값 비교로 범위를 줄이는 탐색법
n = 1,000
log n ≈ 10
n = 1,000,000
log n ≈ 20
n = 1,000,000,000
log n ≈ 30
정리 노트
로그의 마법 — O(log n)
핵심 개념
- O(log n)
- 매번 절반씩 줄이는 알고리즘의 복잡도
- 이진탐색
- 정렬된 배열에서 중간값 비교로 탐색
- 전제 조건
- 배열이 정렬되어 있어야 함
수치 감각
- n=1,000
- 약 10번 비교
- n=1,000,000
- 약 20번 비교
- n=1,000,000,000
- 약 30번 비교
면접에서 '정렬되어 있나요?'라는 질문 한마디가 이진탐색으로 가는 열쇠!
시각 자료
핵심 정리
- 1O(log n) = 매번 반을 버리는 알고리즘
- 2이진탐색: 10억 개도 30번이면 충분
- 3전제: 배열이 정렬되어 있어야 한다
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작