- 순차 탐색과 이진 탐색의 수행 과정을 단계별로 설명할 수 있다.
- 비교 횟수를 기준으로 두 탐색 알고리즘의 효율을 비교·분석할 수 있다.
- 데이터의 상태(정렬 여부)와 사용 상황에 따라 적합한 탐색 방법을 선택할 수 있다.
생각 열기 — 업다운 게임
여러분의 '찾기 전략'은 몇 번 만에 성공할까요?
컴퓨터가 숫자 하나를 숨겼어요. 추측을 입력하면 UP(더 커요) / DOWN(더 작아요)으로 알려 줍니다. 최소 횟수로 찾아보세요!
숫자를 입력하고 [추측!]
혹시 50 → 25 또는 75 → …처럼 가운데만 골라 갔나요? 그렇다면 여러분은 이미 오늘의 주인공 이진 탐색을 발명한 거예요. 1~100 사이라면 어떤 숫자든 최대 7번이면 찾습니다. 왜 7번일까요? 100 → 50 → 25 → 12 → 6 → 3 → 1 — 절반씩 여섯 번 줄이면 후보가 1개만 남고, 그 후보를 확인하는 마지막 한 번까지 더해 최대 7번이거든요!
두 가지 탐색 전략
전부 보기 vs 절반씩 버리기
순차 탐색은 첫 번째부터 하나씩 차례로 확인하는 우직한 방법이에요. 데이터가 정렬되어 있지 않아도 쓸 수 있다는 게 장점이지만, 운이 나쁘면 끝까지(n번) 봐야 하죠.
이진 탐색은 정렬된 데이터에서만 쓸 수 있는 영리한 방법이에요. 한가운데를 확인하고, 찾는 값이 더 크면 왼쪽 절반을, 작으면 오른쪽 절반을 통째로 버립니다. 한 번 비교할 때마다 후보가 절반으로!
같은 목표를 순차 탐색과 이진 탐색으로 각각 찾아 보세요. 이진 탐색에서 반투명해지는 칸들 = 비교 한 번으로 통째로 버려진 후보들입니다!
규모가 커질수록 벌어지는 격차
n번 vs log₂n번 — 자릿수가 다른 세계
슬라이더로 데이터 개수를 늘려 보세요. 최악의 경우 필요한 비교 횟수입니다.
🐢 순차 탐색 (최악)
🚀 이진 탐색 (최악)
그래서, 언제 무엇을 쓸까
| 상황 | 적합한 탐색 | 이유 |
|---|---|---|
| 데이터가 정렬되어 있지 않고, 한 번만 찾으면 됨 | 순차 탐색 | 정렬하는 비용(2차시에서 봤듯 비싸다!)이 아깝다 |
| 데이터가 이미 정렬되어 있음 | 이진 탐색 | 망설일 이유 없음 — log₂n번이면 끝 |
| 정렬은 안 돼 있지만 수없이 자주 찾아야 함 | 정렬 후 이진 탐색 | 정렬은 한 번의 투자, 빠른 탐색은 평생 혜택 |
| 데이터가 계속 추가·삭제됨 | 더 강력한 구조 | 이진 탐색 트리, 해시 등(더 알아보기) — 고급 무기의 세계! |
- 짝과 함께 국어사전(또는 영어사전)을 준비한다. 한 명이 아무 단어나 부른다.
- A 규칙(순차): 첫 페이지부터 차례로 넘기며 찾는다 — 몇 페이지를 넘겼는지 센다. (적당히 하다가 예상 횟수를 계산해도 좋아요!)
- B 규칙(이진): 항상 남은 부분의 한가운데를 펼치고, 앞/뒤 절반을 버리며 찾는다 — 펼친 횟수를 센다.
- 1,000쪽 사전이라면 이론상 B는 최대 몇 번일까? (힌트: 2¹⁰ = 1,024) 실제 횟수와 비교해 보자.
💡 사전이 가나다순으로 정렬되어 있지 않다면 B 규칙이 가능했을까요? — 정렬과 탐색의 운명적인 관계!
확인 문제
바로바로 채점! 해설까지 꼭 읽어 보세요.
3차시 확인 문제
4문항 · 즉시 채점
1이진 탐색을 사용하기 위한 전제 조건은?
2정렬된 데이터 1,024개에서 이진 탐색으로 값을 찾을 때, 후보를 1개로 줄이기까지 필요한 '절반 버리기'는 최대 몇 번인가?
3정렬되지 않은 명단에서 이름 하나를 '딱 한 번' 찾아야 한다. 가장 합리적인 방법은?
4정렬된 데이터 10억 개에서 이진 탐색이 필요한 비교 횟수는 대략?
더 알아보기
교육과정 너머, 궁금한 만큼 깊이!
코딩이진 탐색을 파이썬으로 — 브라우저에서 바로 실행!
업다운 게임의 '컴퓨터 전략'을 코드로 옮기면 이렇습니다. 실행하고, 찾는 값을 바꿔 보세요!
💪 도전: ① target을 데이터에 없는 값(예: 60)으로 바꾸면? ② 순차 탐색 버전을 만들어 비교 횟수를 겨뤄 보세요!
그리고 진짜 대규모 데이터(100만 개)에서 실제 시간을 재 보면 — 계산기의 숫자가 현실이 됩니다:
심화한 번에 찾기 — 해시 탐색의 마법
이진 탐색보다 빠른 게 있을까요? 있습니다 — 해시(hash) 탐색은 평균적으로 단 1번에 찾아요!
비밀은 '주소 계산'이에요. 데이터를 저장할 때 값을 수식(해시 함수)에 넣어 보관할 칸 번호를 계산해 두고, 찾을 때도 같은 수식으로 칸 번호를 계산해 바로 그 칸을 열어 봅니다. 탐색이 아니라 '직행'인 셈이죠.
파이썬의 딕셔너리(dict)가 바로 해시 구조예요 — 4차시에서 만나면 반가워해 주세요! 대신 대가도 있어요: 여분의 저장 공간이 필요하고, '범위 검색'(예: 점수 80~90인 학생들)에는 약합니다. 만능 알고리즘은 없다 — 늘 트레이드오프!
이름을 넣으면 해시 함수가 '보관할 칸 번호'를 즉시 계산합니다. (해시 함수: 글자 코드의 합 % 10)
심화구글은 어떻게 0.5초 만에 찾을까 — 검색 엔진과 인덱스
구글이 수천억 개의 웹 페이지를 매번 순차 탐색한다면 검색 한 번에 며칠이 걸릴 거예요. 비결은 역색인(inverted index) — 책 뒤의 '찾아보기'처럼, 모든 단어마다 "이 단어가 등장하는 페이지 목록"을 미리 정렬해 만들어 둡니다.
검색어가 들어오면 그 단어의 목록을 꺼내 오기만 하면 끝이죠. 우리가 배운 원리 그대로예요 — 찾기 전에 미리 정리(정렬·색인)해 두는 투자가, 매번의 탐색을 극적으로 빠르게 한다. 시험 전에 노트를 정리해 두면 시험 중에 빨리 찾는 것과 같은 이치랍니다.
📄 페이지 A
고양이와 강아지 함께 키우기
📄 페이지 B
강아지 산책 훈련의 모든 것
📄 페이지 C
고양이 사료 고르는 법
| 단어 | 등장 페이지 — 미리 만들어 둔 '찾아보기' |
|---|---|
| 강아지 | A, B |
| 고양이 | A, C |
| 사료 | C |
| 산책 | B |
검색어 버튼을 눌러 보세요 — 페이지를 뒤지지 않고 색인 한 줄만 봅니다!
진로알고리즘이 직업이 되는 곳
- 검색 엔진·추천 시스템 엔지니어 — 수천억 데이터에서 0.1초 안에 찾고 골라내는 알고리즘을 설계해요.
- 데이터베이스 엔지니어 — 은행·게임의 데이터가 빠르게 검색되도록 인덱스와 자료 구조를 다듬어요.
- 알고리즘 트레이더 — 금융 시장에서 마이크로초 단위의 탐색·정렬 알고리즘으로 승부해요.
- 경쟁 프로그래머 — 정보올림피아드(KOI), ICPC 같은 대회에서 알고리즘 실력을 겨뤄요. 고등학생인 지금이 도전 적기!
한눈에 정리
- 순차 탐색: 처음부터 하나씩 — 정렬 불필요, 최악 n번
- 이진 탐색: 가운데 보고 절반 버리기 — 정렬 필수, 최대 약 log₂n번 (10억 개 → 약 30번!)
- 효율 분석의 핵심: 데이터가 커질수록 n번과 log₂n번의 격차는 자릿수가 다른 차이가 된다
- 선택 기준: 정렬 여부 + 탐색 빈도 — 자주 찾을 데이터라면 정렬은 남는 투자
- 정렬(2차시)과 탐색(3차시)은 한 몸 — 그리고 다음 차시부터, 이 모든 것을 직접 코드로 만듭니다 🐍