이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 알고리즘 — 문제 해결의 체계적 접근 → 알고리즘 — 문제 해결의 체계적 접근 → 기초 알고리즘
Learn binary search variants, two pointer, sliding window, and parametric search techniques.
여러분, 탐색이라는 게 뭘까요? 데이터에서 원하는 값을 찾는 거예요.
이건 프로그래밍에서 가장 빈번한 연산이에요. 거의 모든 프로그램의 핵심이죠.
자, 지금 화면에 배열 하나가 보이시죠? 왼쪽이 선형 탐색, 오른쪽이 이진 탐색이에요.
선형 탐색은 앞에서부터 하나씩 확인해야 해요. 1번, 2번, 3번 순서대로요.
최악의 경우 배열 끝까지 가야 하니까, 데이터가 n개면 n번 비교해야 합니다.
그런데 이진 탐색은요? 가운데를 먼저 봐요. 7이 target이면 바로 찾죠.
만약 target이 9라면? 가운데 7보다 크니까 오른쪽 절반만 보면 돼요.
이렇게 매번 절반을 버리니까 비교 횟수가 log n이 되는 거예요.
화면 아래 표를 보세요. 데이터 크기별 비교 횟수 차이가 드라마틱해요.
n이 100이면 선형은 100번, 이진은 겨우 7번이에요.
n이 만 개면? 선형은 만 번인데, 이진은 14번밖에 안 돼요.
n이 백만이면 선형은 백만 번, 이진은 20번. 격차가 5만 배예요.
n이 10억이면요? 선형은 10억 번, 이진은 단 30번입니다.
왜 이런 차이가 날까요? 핵심은 매 단계마다 탐색 범위를 절반으로 줄이기 때문이에요.
2를 30번 곱하면 약 10억이 되거든요. 그래서 log₂(10억)이 약 30인 거예요.
하지만 이진 탐색에는 중요한 전제 조건이 있어요. 배열이 반드시 정렬되어 있어야 해요.
정렬에 O(n log n)이 드는데, 그래도 여러 번 탐색할 거면 이진 탐색이 훨씬 유리합니다.
이번 레슨에서는 이진 탐색뿐 아니라, 투 포인터와 슬라이딩 윈도우도 배울 거예요.
투 포인터는 두 개의 포인터로 정렬 배열에서 조건을 만족하는 쌍을 빠르게 찾는 기법이에요.
슬라이딩 윈도우는 연속 부분 배열 문제를 O(n)에 해결하는 강력한 패턴이에요.
자, 그러면 이진 탐색의 기초부터 시작해볼까요?
선생님: 선형 탐색과 이진 탐색의 가장 큰 차이가 뭘까요?
학생: 선형은 하나씩 보니까 O(n)이고, 이진은 절반씩 줄이니까 O(log n)이요.
선생님: 맞아요! 그런데 이진 탐색을 쓰려면 반드시 필요한 전제 조건이 있어요. 뭘까요?
학생: 배열이 정렬되어 있어야 해요! 정렬 안 되어 있으면 가운데 값과 비교해도 어느 쪽에 있는지 모르니까요.
선생님: 정확해요. 정렬 비용 O(n log n)을 감안해도, 탐색을 여러 번 할 거면 이진 탐색이 압도적으로 유리해요.
학생: 한 번 정렬해 놓으면 여러 번 탐색할 수 있으니까요? 그래서 데이터베이스도 인덱스를 만드는 거군요.
선생님: 바로 그거예요! 정렬은 한 번, 탐색은 여러 번. 이게 실무의 핵심 패턴이에요.