정렬과 탐색 — 자료에 적용하기
정렬과 탐색은 앞에서 배운 모든 것이 만나는 진짜 알고리즘이에요. 자료를 순서대로 줄 세우면(정렬) 원하는 걸 반씩 줄여 빠르게 찾을(탐색) 수 있어요. 그리고 그 안에는 차례대로·되풀이·갈림길 — 우리가 배운 블록들이 다 들어 있어요.
도서관에 책이 번호 순으로 가지런히 꽂혀 있다고 해 봐요.
원하는 책 번호만 알면, 그 근처로 곧장 가서 금방 찾을 수 있어요.
그런데 책이 아무렇게나 뒤죽박죽 쌓여 있다면 어떨까요?
처음부터 한 권씩 다 들춰 봐야 하니, 찾는 데 한참 걸리겠죠.
책을 번호 순으로 줄 세우는 일을 정렬이라고 하고, 그 안에서 원하는 책을 찾는 일을 탐색이라고 해요.
정렬과 탐색은 이렇게 짝을 이뤄요 — 잘 줄 세워 두면(정렬), 훨씬 빠르게 찾을 수 있거든요(탐색).
다만 우리는 책장을 눈으로 쓱 훑지만, 컴퓨터는 한 칸씩 차근차근 봐요 — 그래서 "한 번에 절반을 버린다"는 빠른 탐색의 묘미는, 잠시 뒤 숫자 맞히기로 직접 만져 봐야 진짜 느낄 수 있어요.
줄 세우기 — 버블 정렬로 막대를 키 순서로
막대 여섯 개를 작은 수부터 큰 수 순서로 줄 세워 볼까요? '다음 비교'를 눌러 이웃끼리 견주고, 왼쪽이 크면 자리를 바꿔요.
이 방법을 버블 정렬이라고 해요. 그런데 잘 보면, 네가 누르는 '다음 비교' 한 번 한 번이 앞에서 배운 반복이고, '더 크면 바꾼다'는 판단이 바로 조건이에요 — 컴퓨터는 이 비교를 끝까지 반복으로 자동으로 해요.
빠르게 찾기 — 이진탐색 숫자 맞히기
1부터 100 사이 숫자를 하나 정해 두고, 컴퓨터의 물음에 '더 커요/더 작아요'로 답해 보세요. 몇 번 만에 맞히는지 세어 봐요.
혹시 50 인가요?
이렇게 남은 범위의 가운데를 묻고, 절반을 버리는 방법을 이진탐색이라고 해요. '더 커요/더 작아요'가 바로 앞에서 배운 조건 분기이고, '절반 버리고 또 버림'이 반복이며, '큰 범위를 반으로 나눠 다루는' 솜씨가 바로 큰 문제를 쪼개는 생각이에요.
사전에서 '컴퓨터'를 찾아라 — 하나씩 vs 반씩
같은 낱말을 두 가지 방법으로 찾아봐요 — 첫 장부터 하나씩, 그리고 한가운데서 절반씩. 어느 쪽이 빠른지 견줘 보세요.
| 시도 | 펼친 곳(한가운데) | 펼친 쪽이 '컴퓨터'보다… | 어느 절반을 버리나 | 남은 범위 |
|---|---|---|---|---|
| 1 | 500쪽 | 앞이에요(ㅅ 즈음) | 앞쪽 1~500을 버림 | 501 ~ 1000 |
| 2 | 750쪽 | 앞이에요(ㅈ 즈음) | 앞쪽 501~750을 버림 | 751 ~ 1000 |
| 3 | 875쪽 | 뒤예요(ㅌ 즈음) | 뒤쪽 876~1000을 버림 | 751 ~ 875 |
| 4 | 813쪽 | 앞이에요(거의 다 옴) | 앞쪽 751~813을 버림 | 814 ~ 875 |
| … | … | … | … | 점점 좁아져 곧 820쪽! |
한 번 펼칠 때마다 찾을 범위가 절반씩 줄어요. 1000쪽짜리 사전도 이렇게 하면 열 번 안쪽이면 찾아요 — 한 장씩 넘기는 것과는 비교가 안 되게 빠르죠.
사전이 줄 세워져(정렬돼) 있기 때문에 '절반 버리기'가 가능해요. 만약 낱말이 뒤죽박죽이라면 한가운데를 펼쳐도 앞뒤를 가를 수 없어, 별수 없이 하나씩 봐야 해요 — 그래서 정렬과 탐색은 짝꿍이에요.
이 빠른 찾기 안에는 우리가 배운 게 다 모여 있어요 — '펼친 쪽이 앞이냐 뒤냐' 가르는 판단은 조건, '절반 버리고 또 펼치기'를 되풀이하는 건 반복, '큰 사전을 반으로 나눠 다루는' 솜씨는 큰 문제를 쪼개는 생각이거든요. 정렬도 탐색도, 결국 앞에서 하나하나 배운 블록들이 자료 위에서 만난 거예요.
한 걸음 더 — 정렬이 먼저, 로그적 빠르기, 분할정복, 알고리즘 적는 법
본문만 읽어도 챕터는 완결돼요. 아래는 한 걸음 더 들어가고 싶은 친구를 위한 보너스예요.
1. 정렬돼 있어야 이진탐색이 가능해요
이진탐색이 빠른 데는 숨은 약속이 하나 있어요.
바로 자료가 미리 순서대로 줄 세워져 있어야 한다는 거예요.
한가운데를 펼쳤을 때 '내가 찾는 게 앞쪽일까 뒤쪽일까'를 단번에 가를 수 있는 건, 자료가 정렬돼 있기 때문이거든요.
만약 뒤죽박죽이라면 한가운데가 앞인지 뒤인지 알 수 없어, 절반을 버릴 수가 없어요.
그래서 "먼저 정렬, 그다음 빠른 탐색"이 짝을 이루는 거예요.
2. 반씩 줄이면 얼마나 빠를까 — 로그적 빠르기
1부터 100 사이 숫자를 한 개씩 확인하면, 운이 나쁘면 100번까지 봐야 해요.
그런데 반씩 줄이면 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1, 이렇게 일곱 번이면 후보가 하나로 좁혀져요.
100번이 7번으로 줄어든 거예요.
더 놀라운 건, 자료가 열 배 많은 1~1000이어도 약 열 번이면 충분하다는 점이에요.
자료가 두 배로 늘 때마다 필요한 횟수는 딱 한 번씩만 더 늘거든요.
이렇게 자료가 커져도 천천히만 늘어나는 빠르기를 어른들은 로그적(logarithmic)이라고 불러요.
3. 반으로 나눠 정복하기 — 분할정복
큰 문제를 절반으로 나누고, 그 절반을 또 나눠 가며 다루는 솜씨에는 멋진 이름이 있어요.
바로 분할정복(divide and conquer)이에요.
이진탐색이 매번 범위를 절반으로 나눠 한쪽만 정복해 가는 게 바로 분할정복이에요.
큰 문제를 다루기 좋게 작게 쪼개는 생각을, 한 번이 아니라 반복해서 적용하는 거라고 보면 돼요.
4. 알고리즘을 적는 두 가지 방법
알고리즘을 다른 사람에게 정확히 전할 때 쓰는 표기법이 있어요.
하나는 순서도(flowchart)예요 — 상자와 화살표, 그리고 갈림길을 마름모로 그려 절차를 그림으로 보여 주는 방법이죠.
다른 하나는 의사코드(pseudocode)예요 — 진짜 프로그래밍 언어는 아니지만, 사람이 읽기 쉬운 말로 단계만 또박또박 적어 둔 것이에요.
순서도든 의사코드든, 결국 차례대로·되풀이·갈림길이라는 같은 블록을 다른 모습으로 적은 것일 뿐이에요.
자가진단
외운 사실이 아니라 개념을 적용하는 문제예요. 답을 고르면 바로 정답·오답과 해설을 알려줘요. 틀려도 괜찮아요 — ↻ 다시로 얼마든지 다시 풀 수 있어요.
핵심 정리 — 여기까지 온 너에게
(순차)위에서 아래로 한 번씩
(반복)같은 일을 여러 번
(조건)참·거짓으로 길 고르기
- 우산을 챙길까 순서도 차례대로(순차) 갈림길(조건)
- 버블 정렬 되풀이(반복) 갈림길(조건)
- 이진탐색 쪼개기(분해) 되풀이(반복) 갈림길(조건)
여기까지 잘 왔어요.
처음에 우리는 알고리즘이 "문제를 푸는 정확한 절차"라는 걸 배웠어요.
그 절차는 딱 세 가지 블록 — 차례대로(순차)·되풀이(반복)·갈림길(조건) — 으로 만들어진다는 약속도요.
그다음엔 크고 막막한 문제를 쪼개고·규칙을 찾고·핵심만 남기는 생각 도구로 다루는 법을 익혔고, 마침내 정렬과 탐색이라는 진짜 알고리즘에서 그 모두가 자료 위에서 만나는 걸 봤어요.
처음에 그렸던 '우산을 챙길까' 순서도는 차례대로와 갈림길이었고, 버블 정렬은 되풀이와 갈림길, 이진탐색은 쪼개기와 되풀이와 갈림길이었죠.
이제 너는 어떤 알고리즘을 만나도, 그것을 이 블록들로 나눠서 읽고·만들고·설명할 수 있어요 — 그게 이 책이 너에게 건네고 싶었던 힘이에요.
- 알고리즘은 차례대로·되풀이·갈림길 세 블록으로 만들어져요.
- 큰 문제는 쪼개고·규칙 찾고·핵심만 남겨 다루기 좋게 만든 뒤, 세 블록으로 엮어요.
- 정렬과 탐색은 그 모두가 자료 위에서 만나는 진짜 알고리즘 — 이제 너는 무엇이든 블록으로 나눠 설명할 수 있어요.