검색(Search)은 저장된 자료 가운데 주어진 조건이나 키(Key)에 맞는 레코드를 찾아내는 과정입니다. 자료가 어떤 순서와 구조로 저장되어 있는지에 따라 적합한 검색 방식이 달라지며, 검색 전에 정렬이 필요한 방식도 있고 정렬 없이 바로 사용할 수 있는 방식도 있습니다.
이 장에서는 선형 검색·이진 검색·피보나치 검색·블록 검색·이진 탐색 트리 검색의 원리를 비교하고, 해시 함수를 이용해 키를 저장 위치로 변환하는 해싱의 구조와 충돌·오버플로 해결 방법을 정리합니다.
이 장의 핵심 내용
- 선형 검색은 자료를 처음부터 순서대로 비교하며 정렬이 필요하지 않습니다.
- 이진 검색은 정렬된 자료의 중앙값과 비교해 검색 범위를 절반씩 줄입니다.
- 피보나치 검색은 피보나치 수를 이용해 비교 위치와 검색 구간을 결정합니다.
- 블록 검색은 전체 자료를 여러 블록으로 나눈 뒤 블록 색인과 블록 내부 검색을 결합합니다.
- 이진 탐색 트리는 왼쪽에 작은 키, 오른쪽에 큰 키를 연결하여 검색합니다.
- 해싱은 해시 함수로 키를 해시 테이블의 주소로 변환하는 직접 접근 방식입니다.
- 서로 다른 키가 같은 주소로 변환되는 현상을 충돌이라고 합니다.
- 충돌은 개방 주소법, 체이닝과 재해싱 등으로 처리할 수 있습니다.
검색이란 무엇인가?
검색은 기억장치나 파일에 저장된 자료 가운데 검색 조건을 만족하는 레코드를 찾는 작업입니다. 일반적으로 각 레코드를 구별하는 키를 기준으로 찾으며, 검색에 성공하면 해당 레코드의 위치나 값을 반환하고 실패하면 자료가 없음을 알려 줍니다.
| 용어 | 의미 | 예시 |
|---|---|---|
| 검색 키 | 검색 대상을 구별하는 기준값 | 학번, 사번, 상품번호 |
| 검색 성공 | 키와 일치하는 레코드를 찾음 | 사번 103번의 직원 정보 발견 |
| 검색 실패 | 키와 일치하는 레코드가 없음 | 등록되지 않은 상품번호 |
| 비교 횟수 | 검색 과정에서 키를 대조한 횟수 | 탐색 효율을 판단하는 기준 |
대표 검색 방식은 어떻게 구분할까?
| 검색 방식 | 정렬 필요 여부 | 핵심 원리 | 대표 시간 복잡도 |
|---|---|---|---|
| 선형 검색 | 필요 없음 | 처음부터 차례대로 비교 | O(n) |
| 이진 검색 | 필요 | 중앙값과 비교해 범위를 절반으로 축소 | O(log n) |
| 피보나치 검색 | 필요 | 피보나치 수를 기준으로 구간 분할 | O(log n) |
| 블록 검색 | 블록 간 순서 필요 | 블록 색인 검색 후 블록 내부 탐색 | 구성에 따라 다름 |
| 이진 탐색 트리 검색 | 배열 정렬은 불필요 | 키 비교 결과에 따라 왼쪽·오른쪽 이동 | 평균 O(log n), 최악 O(n) |
| 해싱 | 필요 없음 | 해시 함수로 저장 주소 계산 | 평균 O(1), 최악 O(n) |
선형 검색은 어떻게 동작할까?
선형 검색(Linear Search)은 첫 번째 레코드부터 마지막 레코드까지 키를 하나씩 순서대로 비교하는 가장 단순한 검색 방식입니다. 자료가 정렬되어 있지 않아도 사용할 수 있고 연결 리스트처럼 임의 위치로 바로 이동하기 어려운 구조에도 적용하기 쉽습니다.
검색할 자료가 n개이고 각 위치가 같은 확률로 검색된다고 가정하면, 검색에 성공할 때의 평균 비교 횟수는 다음과 같습니다.
| 항목 | 내용 |
|---|---|
| 사전 정렬 | 필요 없음 |
| 최선 시간 | O(1) — 첫 번째 위치에서 발견 |
| 평균·최악 시간 | O(n) |
| 성공 검색 평균 비교 횟수 | (n+1)/2 |
| 장점 | 구현이 단순하고 자료 구조의 제약이 적음 |
| 단점 | 자료가 많아질수록 비교 횟수가 증가 |
시험 포인트: 선형 검색의 성공 검색 평균 비교 횟수는 (n+1)/2입니다. 검색 실패 시에는 일반적으로 모든 자료를 확인하므로 n회 비교합니다.
이진 검색은 어떻게 동작할까?
이진 검색(Binary Search)은 정렬된 자료의 중앙값과 검색 키를 비교하고, 검색 키가 중앙값보다 작으면 왼쪽 절반, 크면 오른쪽 절반만 다시 검색합니다. 비교할 때마다 검색 대상이 되는 자료 수가 대략 절반으로 줄어듭니다.
- 정렬된 자료에서 가장 왼쪽 위치와 오른쪽 위치를 정합니다.
- 두 위치의 중앙 인덱스를 계산합니다.
- 검색 키와 중앙값이 같으면 검색에 성공합니다.
- 검색 키가 작으면 오른쪽 경계를 중앙값 왼쪽으로 옮깁니다.
- 검색 키가 크면 왼쪽 경계를 중앙값 오른쪽으로 옮깁니다.
- 검색 범위가 없어질 때까지 반복합니다.
이진 검색의 비교 예시
정렬된 자료 2, 5, 7, 11, 14, 18, 23에서 18을 검색한다고 가정합니다.
| 단계 | 검색 범위 | 중앙값 | 판단 |
|---|---|---|---|
| 1단계 | 2, 5, 7, 11, 14, 18, 23 | 11 | 18이 더 크므로 오른쪽 탐색 |
| 2단계 | 14, 18, 23 | 18 | 검색 성공 |
| 항목 | 내용 |
|---|---|
| 필수 조건 | 자료가 검색 키 기준으로 정렬되어 있어야 함 |
| 최선 시간 | O(1) — 첫 중앙값에서 발견 |
| 평균·최악 시간 | O(log n) |
| 장점 | 자료가 많아도 비교 횟수가 비교적 적음 |
| 단점 | 삽입·삭제가 잦으면 정렬 상태 유지 비용이 발생 |
피보나치 검색은 무엇일까?
피보나치 검색(Fibonacci Search)은 이진 검색과 비슷하게 정렬된 자료의 검색 범위를 줄여 나가지만, 중앙 위치 대신 피보나치 수를 이용해 비교 위치와 다음 검색 구간을 정합니다.
피보나치 수열은 앞의 두 수를 더해 다음 수를 만드는 수열입니다.
| 항목 | 내용 |
|---|---|
| 필수 조건 | 자료가 정렬되어 있어야 함 |
| 분할 기준 | 피보나치 수 |
| 시간 복잡도 | O(log n) |
| 특징 | 비교 위치 계산에서 덧셈과 뺄셈을 중심으로 활용 가능 |
| 시험 구분 | 이진 검색은 절반, 피보나치 검색은 피보나치 수로 구간 결정 |
블록 검색은 어떻게 동작할까?
블록 검색(Block Search)은 전체 레코드를 일정한 크기의 블록으로 나눈 뒤, 먼저 블록별 대표 키나 색인을 검색하고 선택된 블록 내부에서 원하는 키를 찾는 방식입니다.
블록 사이에는 키의 순서가 유지되어야 하지만, 하나의 블록 내부는 반드시 완전히 정렬되어 있을 필요는 없습니다. 따라서 색인 영역에서는 빠른 검색을 사용하고 블록 내부에서는 선형 검색을 사용할 수 있습니다.
1단계: 블록 선택
각 블록의 대표 키나 최댓값을 저장한 색인을 검색하여 목표 키가 포함될 블록을 결정합니다.
2단계: 블록 내부 검색
선택된 블록 안에서 레코드를 순서대로 비교하거나 별도의 내부 검색 방식을 사용합니다.
핵심 구분: 블록 검색은 전체 자료를 한 번에 선형 검색하는 방식과 달리, 먼저 검색 범위를 특정 블록으로 줄인 뒤 그 안에서 다시 검색합니다.
이진 탐색 트리 검색은 무엇일까?
이진 탐색 트리(Binary Search Tree)는 각 노드의 왼쪽 부분 트리에는 더 작은 키를, 오른쪽 부분 트리에는 더 큰 키를 저장하는 자료 구조입니다. 검색 키와 현재 노드의 키를 비교하면서 왼쪽이나 오른쪽으로 이동합니다.
- 루트 노드에서 검색을 시작합니다.
- 검색 키가 현재 노드와 같으면 성공합니다.
- 검색 키가 작으면 왼쪽 자식으로 이동합니다.
- 검색 키가 크면 오른쪽 자식으로 이동합니다.
- 더 이동할 노드가 없으면 검색에 실패합니다.
| 트리 상태 | 검색 높이 | 시간 복잡도 |
|---|---|---|
| 균형에 가까운 트리 | 약 log n | 평균 O(log n) |
| 한쪽으로 치우친 트리 | 최대 n | 최악 O(n) |
검색 방식을 한눈에 비교하면?
| 구분 | 선형 검색 | 이진 검색 | 피보나치 검색 | 블록 검색 | 이진 탐색 트리 |
|---|---|---|---|---|---|
| 정렬 조건 | 불필요 | 필요 | 필요 | 블록 간 순서 필요 | 트리 규칙 유지 |
| 검색 기준 | 순차 비교 | 중앙값 | 피보나치 수 | 블록 색인 | 노드 키 비교 |
| 대표 효율 | O(n) | O(log n) | O(log n) | 구성에 따라 다름 | 평균 O(log n) |
| 주요 장점 | 구현이 단순 | 비교 횟수가 적음 | 덧셈 중심의 구간 계산 | 검색 범위를 블록으로 축소 | 삽입·검색을 함께 지원 |
| 주요 단점 | 자료가 많으면 느림 | 정렬 유지 필요 | 구현이 복잡함 | 블록·색인 설계 필요 | 편향되면 O(n) |
해싱이란 무엇인가?
해싱(Hashing)은 레코드의 키를 해시 함수(Hash Function)에 입력하여 해시 테이블(Hash Table)에서 사용할 주소 또는 인덱스를 계산하고, 그 위치를 통해 레코드에 접근하는 방식입니다.
배열의 앞에서부터 차례로 찾는 대신 키에서 저장 위치를 직접 계산하기 때문에 평균적으로 매우 빠른 검색·삽입·삭제가 가능합니다. 다만 여러 키가 같은 위치로 계산되면 충돌을 해결해야 합니다.
| 항목 | 내용 |
|---|---|
| 접근 방식 | 키로 저장 주소를 계산하는 직접 접근 |
| 평균 검색 시간 | O(1) |
| 최악 검색 시간 | O(n) |
| 사전 정렬 | 필요 없음 |
| 장점 | 검색·삽입·삭제가 평균적으로 빠름 |
| 단점 | 충돌 처리와 추가 저장공간이 필요할 수 있음 |
해시 테이블의 주요 용어는 무엇일까?
| 용어 | 의미 |
|---|---|
| 해시 함수 | 키를 해시 테이블의 주소나 인덱스로 변환하는 함수 |
| 해시 주소 | 해시 함수가 계산한 저장 위치 |
| 홈 주소 | 해시 함수가 키에 대해 처음 계산한 기본 주소 |
| 해시 테이블 | 해시 주소를 기준으로 레코드를 저장하는 표 |
| 슬롯 | 일반적으로 하나의 레코드를 저장할 수 있는 최소 공간 |
| 버킷 | 하나 이상의 슬롯을 묶은 저장 단위로 설명될 수 있음 |
| 충돌 | 서로 다른 키가 같은 해시 주소로 계산되는 현상 |
| 동의어 | 동일한 홈 주소로 해시되어 충돌 관계에 있는 키 또는 레코드의 집합 |
| 오버플로 | 충돌로 인해 해당 버킷이나 저장 위치의 수용 범위를 넘는 현상 |
용어 주의: 버킷과 슬롯의 사용 방식은 자료마다 다를 수 있습니다. 시험에서는 제시된 정의를 따르되, 일반적으로 슬롯은 개별 저장 위치이고 버킷은 하나 이상의 슬롯을 포함하는 논리적 단위로 이해하면 됩니다.
충돌과 오버플로는 어떻게 다를까?
충돌(Collision)은 서로 다른 키가 같은 홈 주소로 계산되는 현상입니다. 오버플로(Overflow)는 충돌한 데이터를 저장하려고 할 때 해당 주소나 버킷에 더 이상 저장할 공간이 없는 상태를 의미합니다.
| 구분 | 발생 의미 | 예시 |
|---|---|---|
| 충돌 | 두 키가 같은 주소를 가짐 | 21 mod 10과 31 mod 10이 모두 1 |
| 오버플로 | 해당 저장공간의 수용 범위를 초과 | 충돌한 레코드를 현재 버킷에 더 저장할 수 없음 |
좋은 해시 함수는 어떤 조건을 갖춰야 할까?
- 계산이 간단해야 합니다. 주소 계산 자체가 복잡하면 직접 접근의 장점이 줄어듭니다.
- 키를 고르게 분산해야 합니다. 특정 주소에 키가 집중되면 충돌이 증가합니다.
- 모든 테이블 위치를 충분히 활용해야 합니다. 사용되지 않는 슬롯이 지나치게 많으면 공간 효율이 떨어집니다.
- 키의 규칙성에 덜 민감해야 합니다. 비슷한 키가 같은 주소로 몰리지 않도록 설계해야 합니다.
해시 함수에는 어떤 종류가 있을까?
제산 방법
제산 방법(Division Method)은 키를 테이블 크기와 관련된 정수로 나눈 나머지를 해시 주소로 사용합니다. 나누는 수는 키 분포를 고르게 만들 수 있도록 선택하며, 일반적으로 테이블 크기와 가까운 소수를 사용하는 방식이 널리 알려져 있습니다.
중간 제곱 방법
중간 제곱 방법(Mid-Square Method)은 키를 제곱한 뒤 결과의 중간 부분에 있는 자릿수나 비트를 추출하여 주소로 사용합니다. 사용할 중간 자릿수의 개수는 해시 테이블의 크기에 맞게 정합니다.
비트 기준 예: 주소로 n비트를 사용하면 표현 가능한 주소 수는 2n개입니다. 실제 테이블 크기가 반드시 2n이어야 하는 것은 아니지만, n비트 주소 체계에서는 최대 2n개의 서로 다른 값을 표현할 수 있습니다.
중첩 방법
중첩 방법(Folding Method)은 키를 일정한 길이의 여러 부분으로 나눈 뒤 각 부분을 더하거나 배타적 논리합(XOR)하여 주소를 구합니다. 긴 키를 여러 조각으로 접어서 하나의 값으로 만든다고 이해할 수 있습니다.
기수 변환 방법
기수 변환 방법(Radix Conversion Method)은 키를 다른 진법의 수로 간주하여 변환한 뒤, 변환 결과의 일부를 해시 주소로 사용하는 방식입니다.
계수 분석 방법
계수 분석 방법(Digit Analysis Method)은 키의 각 자릿수 분포를 분석하여 비교적 고르게 분포된 자릿수를 선택하고, 선택한 자릿수로 해시 주소를 구성합니다. 키의 통계적 특성을 미리 분석할 수 있을 때 사용할 수 있습니다.
| 방법 | 핵심 처리 | 기억할 표현 |
|---|---|---|
| 제산 방법 | 키를 나눈 나머지 사용 | mod 연산 |
| 중간 제곱 방법 | 키를 제곱하고 중간 자릿수 추출 | 제곱 후 중앙 |
| 중첩 방법 | 키를 분할해 합 또는 XOR | 나누고 접기 |
| 기수 변환 방법 | 키를 다른 진법으로 변환 | 진법 변환 |
| 계수 분석 방법 | 분포가 고른 자릿수 선택 | 자릿수 분포 분석 |
충돌과 오버플로는 어떻게 해결할까?
선형 개방 주소법
선형 개방 주소법(Linear Open Addressing), 즉 선형 조사법(Linear Probing)은 홈 주소가 이미 사용 중이면 다음 슬롯을 차례대로 확인하여 처음 발견한 빈 슬롯에 데이터를 저장합니다.
| 장점 | 단점 |
|---|---|
| 포인터와 별도 연결 공간이 필요하지 않음 | 연속된 영역에 데이터가 몰리는 1차 군집화가 발생할 수 있음 |
| 자료가 적고 적재율이 낮을 때 단순하고 효율적 | 삭제 시 탐색 경로를 보존하기 위한 별도 표시가 필요할 수 있음 |
폐쇄 주소법과 체이닝
폐쇄 주소법(Closed Addressing)은 같은 해시 주소로 변환된 데이터를 해당 주소에 연결된 별도 구조에 저장하는 방식입니다. 대표적인 방법이 체이닝(Chaining)이며, 각 버킷에 연결 리스트를 두어 충돌한 레코드를 연결합니다.
| 장점 | 단점 |
|---|---|
| 한 주소에 여러 레코드를 연결할 수 있음 | 포인터 또는 연결 구조를 위한 추가 공간 필요 |
| 테이블 슬롯 수보다 많은 레코드 저장 가능 | 충돌이 많으면 연결 리스트 탐색 시간이 증가 |
| 삭제 처리가 비교적 자연스러움 | 메모리 접근이 분산되어 캐시 효율이 낮아질 수 있음 |
재해싱
재해싱(Rehashing)은 충돌이 발생했을 때 다른 해시 함수를 적용하여 대체 주소를 계산하는 방식입니다. 문맥에 따라 테이블의 크기를 늘린 뒤 모든 항목의 주소를 다시 계산하는 작업을 뜻하기도 합니다.
시험 용어 주의: 문제에서 재해싱을 “충돌 시 새로운 해시 함수를 적용하는 방법”으로 제시하면 해당 정의를 따릅니다. 일반 자료구조 문맥에서는 테이블 확장 후 전체 항목의 주소를 다시 계산하는 의미로도 사용됩니다.
개방 주소법과 체이닝은 어떻게 다를까?
| 구분 | 개방 주소법 | 체이닝 |
|---|---|---|
| 충돌 데이터 저장 위치 | 해시 테이블 내부의 다른 빈 슬롯 | 해당 버킷에 연결된 리스트 |
| 추가 포인터 | 일반적으로 불필요 | 필요 |
| 적재율 | 1을 넘을 수 없음 | 1을 넘을 수 있음 |
| 삭제 처리 | 삭제 표식이 필요할 수 있음 | 연결 리스트에서 제거 |
| 성능 저하 원인 | 빈 슬롯 감소와 군집화 | 연결 리스트 길이 증가 |
적재율은 해싱 성능에 어떤 영향을 줄까?
적재율(Load Factor)은 해시 테이블의 슬롯 수에 비해 얼마나 많은 레코드가 저장되어 있는지를 나타냅니다. 저장된 레코드 수를 n, 슬롯 수를 m이라고 하면 적재율 α는 다음과 같습니다.
적재율이 높아질수록 충돌 가능성이 커지고 검색 성능이 저하될 수 있습니다. 개방 주소법은 모든 레코드를 테이블 내부 슬롯에 저장하므로 적재율이 1을 넘을 수 없지만, 체이닝은 한 버킷에 여러 레코드를 연결할 수 있어 적재율이 1을 넘을 수 있습니다.
시험에서 자주 혼동되는 개념
선형 검색과 선형 조사법
선형 검색은 자료를 처음부터 비교하는 검색 알고리즘이고, 선형 조사법은 해시 충돌 시 다음 빈 슬롯을 찾는 해결 방법입니다.
충돌과 동의어
충돌은 현상이고, 동의어는 동일한 홈 주소로 해시되어 충돌 관계에 있는 키나 레코드의 집합입니다.
충돌과 오버플로
같은 주소가 계산되면 충돌이고, 충돌 데이터를 저장할 공간까지 부족해지면 오버플로입니다.
개방 주소법과 폐쇄 주소법
개방 주소법은 테이블 내부의 다른 슬롯을 사용하고, 폐쇄 주소법은 원래 주소에 연결된 별도 구조에 충돌 데이터를 저장합니다.
이번 장 핵심 요약
- 검색은 저장된 자료에서 주어진 키와 일치하는 레코드를 찾는 작업입니다.
- 선형 검색은 정렬 없이 사용할 수 있으며 성공 검색 평균 비교 횟수는 (n+1)/2입니다.
- 이진 검색은 정렬된 자료에서 검색 범위를 절반씩 줄이며 O(log n)입니다.
- 피보나치 검색은 피보나치 수를 기준으로 검색 위치와 구간을 결정합니다.
- 블록 검색은 색인으로 블록을 정한 뒤 블록 내부를 검색합니다.
- 이진 탐색 트리는 왼쪽에 작은 키, 오른쪽에 큰 키를 저장합니다.
- 해싱은 해시 함수로 키를 해시 테이블 주소로 변환합니다.
- 서로 다른 키가 같은 주소로 변환되는 현상은 충돌입니다.
- 제산법은 나머지, 중간 제곱법은 제곱 결과의 중앙, 중첩법은 분할한 값의 합이나 XOR을 사용합니다.
- 개방 주소법은 테이블 내부의 빈 슬롯을 찾고, 체이닝은 연결 리스트로 충돌 데이터를 저장합니다.
- 적재율이 높아질수록 일반적으로 해시 테이블의 검색 성능은 저하됩니다.
복습 문제
정렬되지 않은 자료를 처음부터 순서대로 비교하는 검색은?
선형 검색입니다.
선형 검색의 성공 검색 평균 비교 횟수는?
(n+1)/2회입니다.
검색 전에 자료가 반드시 정렬되어 있어야 하는 대표 검색은?
이진 검색과 피보나치 검색입니다.
이진 검색에서 한 번 비교할 때마다 검색 범위는 어떻게 변할까?
검색 대상이 되는 범위가 대략 절반으로 줄어듭니다.
피보나치 수열 1, 2, 3, 5, 8 다음 수는?
13입니다.
해시 함수에서 키를 여러 부분으로 나눈 뒤 더하거나 XOR하는 방식은?
중첩 방법(Folding Method)입니다.
해싱에서 서로 다른 키가 같은 주소로 변환되는 현상은?
충돌(Collision)입니다.
동일한 홈 주소로 인해 충돌 관계에 있는 레코드의 집합은?
동의어(Synonym)입니다.
충돌이 발생하면 다음 빈 슬롯을 차례대로 찾는 방식은?
선형 개방 주소법 또는 선형 조사법입니다.
버킷에 연결 리스트를 두어 충돌 데이터를 연결하는 방식은?
체이닝(Chaining)입니다.
개방 주소법, 폐쇄 주소법, 로그 주소법, 재해싱 중 해시 테이블의 오버플로 처리 기법이 아닌 것은?
로그 주소법입니다. 대표적인 처리 방식에는 개방 주소법, 체이닝과 재해싱 등이 있습니다.
이진 검색과 선형 검색 중 정렬이 필수인 것은?
이진 검색입니다. 선형 검색은 정렬되지 않은 자료에도 사용할 수 있습니다.
참고자료
- 학습 범위 — 사무자동화산업기사 제1과목 사무자동화 시스템, 검색과 해싱
- Q-Net — 사무자동화산업기사 종목별 상세정보 및 출제기준
- NIST Dictionary of Algorithms and Data Structures — Linear Search
- NIST Dictionary of Algorithms and Data Structures — Hash Table
- NIST Dictionary of Algorithms and Data Structures — Collision Resolution Scheme
- NIST Dictionary of Algorithms and Data Structures — Chaining
- NIST Dictionary of Algorithms and Data Structures — Load Factor
이 글은 사무자동화산업기사 시험 범위에 포함된 검색과 해싱을 이해하고 복습할 수 있도록 재구성한 정리입니다. 검색과 해시 테이블의 실제 성능은 자료의 크기, 정렬 상태, 트리 균형, 해시 함수의 분포, 적재율과 충돌 처리 방식에 따라 달라질 수 있습니다. 버킷·슬롯·재해싱과 같은 용어는 자료에 따라 정의 범위가 다를 수 있으므로 실제 시험에서는 문제에서 제시한 정의와 조건을 우선 확인해야 합니다.