코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
알고리즘 — 문제 해결의 체계적 접근 → 기초 알고리즘
탐색 알고리즘은 데이터에서 원하는 값을 찾는 기법입니다. 프로그래밍에서 가장 빈번하게 수행되는 연산이며, 효율적인 탐색은 프로그램 성능을 결정짓는 핵심 요소입니다.
선형 탐색(Linear Search): 배열의 앞에서부터 하나씩 비교합니다. 시간복잡도 O(n)으로, 정렬 여부와 무관하게 동작합니다. 하지만 데이터가 클수록 비효율적입니다.
이진 탐색(Binary Search): 정렬된 배열에서 가운데를 기준으로 탐색 범위를 절반씩 줄입니다. 시간복잡도 O(log n)으로, 10억 개 데이터에서도 단 30번 비교로 답을 찾습니다.
투 포인터(Two Pointer): 두 개의 포인터를 활용해 정렬된 배열에서 조건을 만족하는 쌍을 O(n)에 찾습니다.
슬라이딩 윈도우(Sliding Window): 고정 또는 가변 크기의 윈도우를 이동시키며 연속 부분 배열 문제를 O(n)에 해결합니다.
이 레슨에서는 이진탐색의 기초부터 Parametric Search까지, 투 포인터와 슬라이딩 윈도우의 핵심 패턴을 모두 다룹니다.
여러분, 탐색이라는 게 뭘까요? 데이터에서 원하는 값을 찾는 거예요.
이건 프로그래밍에서 가장 빈번한 연산이에요. 거의 모든 프로그램의 핵심이죠.
자, 지금 화면에 배열 하나가 보이시죠? 왼쪽이 선형 탐색, 오른쪽이 이진 탐색이에요.
선형 탐색은 앞에서부터 하나씩 확인해야 해요. 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)에 해결하는 강력한 패턴이에요.
자, 그러면 이진 탐색의 기초부터 시작해볼까요?