§ 1 · 절차알고리즘이란
알고리즘(algorithm)은 복잡한 단어처럼 보이지만 실제로는 그렇지 않다. 알고리즘은 단순히 문제를 해결하기 위한 특정 절차다.
시리얼 한 그릇을 준비하는 것도 알고리즘이다. ① 그릇을 집고 ② 시리얼을 붓고 ③ 우유를 붓고 ④ 숟가락을 담근다. 컴퓨팅에서 알고리즘은 특정 작업을 수행하기 위한 절차다. 같은 작업을 달성하는 방법은 여러 가지이며, 그 선택이 코드를 빠르게도 느리게도 만든다.
for 루프도 "리스트의 모든 항목을 출력한다"는 문제를 푸는 하나의 알고리즘이다.
§ 2 · 항상 정렬정렬된 배열
정렬된 배열(ordered array)은 일반 배열과 거의 같지만, 값들이 항상 정렬 상태를 유지해야 한다는 차이가 있다. 값을 추가할 때마다 순서가 유지되도록 적절한 셀에 끼워 넣는다.
배열 [3, 17, 80, 202]에 75를 넣는다고 하자. 일반 배열이라면 끝에 1단계로 붙이면 끝이다. 그러나 정렬된 배열에서는 먼저 올바른 위치를 탐색한 뒤, 자리를 만들기 위해 더 큰 값들을 밀어야 한다.
선형 탐색조차 정렬된 배열에서는 조금 빨라진다. [3, 17, 75, 80, 202]에서 22를 찾을 때, 75에 도달하는 순간 멈출 수 있다 — 22가 75 오른쪽에 있을 수 없기 때문이다.
def linear_search(array, value) array.each do |element| # 찾으면 즉시 반환 if element == value return value # 찾는 값보다 큰 원소를 만나면 일찍 탈출 elsif element > value break end end return nil end
§ 3 · 절반씩 버리기이진 탐색
1과 100 사이 숫자 맞히기 게임을 떠올려 보자. 1부터 부르지 않는다. 정중앙 50으로 시작한다. 더 높든 낮든, 한 번에 가능한 숫자의 절반을 제거하기 때문이다. 이것이 이진 탐색(binary search)의 본질이다.
아래 모션은 9개 원소의 정렬된 배열에서 값 7을 이진 탐색으로 찾는다. 매번 가운데를 보고, 찾는 값이 있을 수 없는 절반을 통째로 버린다.
def binary_search(array, value) lower_bound = 0 upper_bound = array.length - 1 while lower_bound <= upper_bound do midpoint = (upper_bound + lower_bound) / 2 value_at_midpoint = array[midpoint] if value < value_at_midpoint upper_bound = midpoint - 1 elsif value > value_at_midpoint lower_bound = midpoint + 1 elsif value == value_at_midpoint return midpoint end end return nil end
§ 4 · 폭발적인 격차이진 탐색 vs 선형 탐색
작은 배열에서는 두 알고리즘 차이가 크지 않다. 그러나 데이터가 커지면 격차가 폭발한다. 핵심 패턴은 이것이다 — 정렬된 배열의 항목 수를 두 배로 늘릴 때마다, 이진 탐색은 단 1단계만 더 든다.
| 배열 크기 | 선형 탐색 | 이진 탐색 |
|---|---|---|
| 100 | 100단계 | 7단계 |
| 10,000 | 10,000단계 | 13단계 |
| 1,000,000 | 1,000,000단계 | 20단계 |
§ 5 · 정리이 장이 남긴 것
특정 목표를 달성하는 방법은 종종 여러 가지이고, 선택한 알고리즘은 코드 속도에 심각한 영향을 미친다. 그러나 정렬된 배열이 이진 탐색을 허용한다고 해서 항상 정렬된 배열을 써야 하는 것은 아니다 — 삽입이 잦다면 일반 배열이 나을 수 있다. 경쟁 알고리즘을 분석하는 방법은 각각이 거치는 단계 수를 세는 것이다.
다음 장에서는 이 단계 수를 표현하는 공식적인 언어, Big O 표기법을 배운다.