검색 알고리즘 & 해싱
순차·이진·보간 검색 + 해시 함수 · 충돌 처리(체이닝·개방주소법).
이진 검색의 시간복잡도 O(log n)과 해시 충돌 처리 방식(선형 조사·이차 조사·체이닝)이 단답으로 반복 출제된다.
검색(Search)은 주어진 데이터 집합에서 원하는 값을 찾는 작업이다. 데이터 정렬 여부와 접근 방식에 따라 시간복잡도가 크게 달라진다.
| 검색 방법 | 요구 조건 | 시간복잡도 | 설명 |
|---|---|---|---|
| 순차 검색 (Linear) | 없음 | O(n) | 처음부터 차례로 비교 |
| 이진 검색 (Binary) | 정렬된 배열 | O(log n) | 중간 값과 비교 후 반쪽 버림 |
| 보간 검색 (Interpolation) | 정렬 + 균일 분포 | O(log log n) 평균 | 값 분포로 위치 예측 |
| 해시 검색 (Hashing) | 해시 함수 | O(1) 평균 | 키 → 인덱스 직접 계산 |
이진 검색 PASS 공식 — 이미 정렬된 배열에서 중간 요소와 비교 → 작으면 왼쪽, 크면 오른쪽으로 검색 범위를 반씩 좁혀나간다. n개 데이터 검색에 최대 log₂(n) + 1 번 비교.
-- 이진 검색 의사 코드
low = 0
high = n - 1
while low <= high:
mid = (low + high) / 2
if a[mid] == key:
return mid -- 찾음
elif a[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1 -- 없음해싱(Hashing) 은 키를 해시 함수에 넣어 얻은 주소로 직접 접근하는 방식이다. 평균 O(1)의 검색 시간을 제공하지만, 두 키의 해시 값이 같아지는 충돌(Collision) 이 문제가 된다.
| 해시 함수 종류 | 원리 |
|---|---|
| 제산법 (Division) | key % m (가장 널리 쓰임) |
| 중간 제곱법 | key² 의 중간 자릿수 사용 |
| 폴딩법 (Folding) | 키를 여러 조각으로 나눠 더하기 |
| 숫자 분석법 | 키의 분포 분석해 특정 자릿수 선택 |
| 기수 변환법 | 다른 진수로 변환 후 사용 |
| 충돌 처리 | 방식 | 특징 |
|---|---|---|
| 선형 조사 (Linear Probing) | 충돌 시 다음 빈 슬롯 탐색 | 1차 군집(Clustering) 문제 |
| 이차 조사 (Quadratic Probing) | i² 간격으로 탐색 | 1차 군집 완화 |
| 이중 해싱 (Double Hashing) | 제2 해시 함수로 간격 결정 | 군집 현상 거의 없음 |
| 체이닝 (Chaining) | 같은 버킷에 연결 리스트 연결 | 구현 단순, 메모리 추가 |
체이닝 vs 개방 주소법 — 체이닝은 추가 메모리를 쓰지만 삭제가 쉽다. 선형·이차·이중 해싱은 개방 주소법(Open Addressing) 에 속하며 추가 메모리 없이 해시 테이블 내부에서 해결한다.
적재율(Load Factor, α) — 해시 테이블의 채워진 비율. α = 저장된 키 수 / 버킷 수. α가 높을수록 충돌이 많아지며, 일반적으로 0.7 이하로 유지하는 것이 권장된다.
이진 검색(Binary Search)의 평균 시간복잡도는?
정렬된 배열 [1, 3, 5, 7, 9, 11, 13, 15]에서 이진 검색으로 숫자 11을 찾을 때 비교 횟수는?
해시 충돌 시 같은 버킷에 연결 리스트 형태로 저장하는 처리 방식은?
해시 테이블에서 충돌이 발생했을 때 다음 빈 슬롯을 순차적으로 찾아 저장하는 개방 주소법 기법을 ( )(이)라 한다.
가장 널리 쓰이는 해시 함수로, 키를 특정 정수(테이블 크기)로 나눈 나머지를 해시 값으로 쓰는 방법은?
해싱의 평균 검색 시간복잡도는 O(1) 이다.