검색·해싱·복잡도와 파일 구조

네 영역을 구분하는 기준

이 이론은 서로 다른 네 질문을 한꺼번에 다룬다. 검색은 자료 안에서 목표 키를 찾는 절차, 해싱은 키로 저장 위치를 계산하는 방법, 복잡도는 입력 크기에 따른 비용 증가율, 파일 구조는 보조기억장치에서 레코드를 배치하고 접근하는 방식이다. 같은 키를 사용하더라도 분석 대상이 다르므로 용어를 섞지 않는다.

순차 검색과 이진 검색

두 검색의 입력 전제

순차 검색(Sequential Search, Linear Search)은 첫 원소부터 목표 키와 하나씩 비교한다. 정렬되지 않은 배열이나 연결 리스트에도 적용할 수 있다. 첫 원소가 목표라면 Θ(1)이지만, 목표가 마지막에 있거나 없으면 n개를 확인하므로 최악은 Θ(n)이다.

이진 검색(Binary Search)은 정렬된 구간의 중간 원소와 목표를 비교하고, 목표가 있을 수 없는 절반을 버리는 과정을 반복한다. 배열처럼 중간 인덱스에 Θ(1)로 접근할 수 있는 자료구조를 전제로 하면 최악 Θ(log n)이다. 단순 연결 리스트에서는 중간 노드까지 이동하는 비용이 들기 때문에 비교 횟수는 줄어도 전체 탐색 시간이 일반적으로 Θ(log n)이 되지 않는다.

평균 시간은 목표 위치가 균등하게 나타난다는 등의 분석 가정에 따라 달라질 수 있다. 시험에서는 먼저 정렬 전제와 중간 위치 접근 비용을 확인한다.

low·high·mid 추적

정렬 배열 [2, 5, 8, 12, 16, 23, 38]에서 16을 찾는다고 하자. 인덱스는 0부터 시작하며 mid = low + (high - low) // 2를 사용한다.

목표가 없으면 갱신을 반복한 뒤 low > high가 되는 순간 실패로 종료한다. low = mid 또는 high = mid처럼 중간 위치를 다시 포함하면 같은 구간이 반복될 수 있으므로, 불일치 시에는 mid + 1 또는 mid - 1로 이동한다.

(low + high) // 2도 수학적으로 같은 중간값을 만들지만, 고정 폭 정수형 언어에서는 합이 범위를 넘을 수 있다. low + (high - low) // 2는 이 오버플로 위험을 줄이는 표현이다.

중복 키와 정렬 비용

일반 이진 검색은 중복 값 중 어느 한 위치를 찾으면 끝난다. 첫 번째 위치를 찾으려면 일치했을 때 결과를 저장하고 왼쪽 구간을 계속 탐색하며, 마지막 위치는 오른쪽 구간을 계속 탐색한다. 따라서 “이진 검색은 항상 첫 번째 중복 원소를 반환한다”는 선지는 틀리다.

정렬되지 않은 자료를 한 번만 검색하려고 먼저 정렬하면, 정렬 비용이 검색 절감보다 클 수 있다. 반대로 같은 자료를 여러 번 검색한다면 한 번의 정렬·색인 구축 비용을 여러 질의에 나눌 수 있다. 검색 알고리즘만 비교하지 말고 전처리 비용, 질의 횟수, 갱신 빈도를 함께 본다.

해싱과 충돌 처리

해시 함수와 해시 테이블

해시 함수(Hash Function)는 키를 제한된 정수 범위의 주소로 변환한다. 해시 테이블(Hash Table)은 그 주소를 배열의 위치나 버킷으로 사용하여 레코드를 저장하는 자료구조다. 키 k의 최초 계산 위치를 홈 주소 또는 홈 버킷이라고 한다.

서로 다른 키가 같은 홈 주소로 변환되는 현상이 충돌(Collision)이다. 같은 홈 주소를 얻은 키들을 동의어(Synonym)라고 부르기도 한다. 충돌로 인해 예정된 버킷이나 탐사 가능한 영역에 더 저장할 공간이 부족한 상태는 오버플로(Overflow)다. 충돌은 일반적인 해시 테이블에서 발생 가능한 정상 상황이며, 해시 함수가 무조건 잘못되었다는 뜻이 아니다.

대표적인 해시 함수 구성법

좋은 해시 함수는 계산이 지나치게 복잡하지 않으면서 키를 가능한 한 고르게 분산한다. 그러나 일반적인 유한 크기 테이블에서 가능한 키의 수가 더 많다면 충돌 가능성을 완전히 없앨 수 없다.

체이닝과 개방 주소법

충돌 해결은 저장 위치가 테이블 밖의 연결 구조까지 확장되는지, 모든 항목을 테이블 내부에 두는지로 먼저 나눈다.

선형 탐사의 대표 식은 h_i(k) = (h(k) + i) mod m이다. 이중 해싱은 h_i(k) = (h₁(k) + i × h₂(k)) mod m으로 표현할 수 있다. 모든 슬롯을 방문하려면 h₂(k)와 테이블 크기 m이 서로소가 되도록 정하는 등의 조건이 필요하다.

개방 주소법에서는 항목을 모두 테이블 내부에 저장하므로 빈 슬롯이 있어야 한다. 삭제한 칸을 단순한 EMPTY로 바꾸면 그 뒤에 저장된 충돌 키의 탐색이 중간에서 끊길 수 있다. 따라서 보통 DELETED와 같은 삭제 표시(Tombstone)를 두어 탐사열은 유지하면서 이후 삽입에 재사용한다.

충돌 직접 추적

버킷 수가 7이고 h(k) = k mod 7일 때 키 10, 17, 24, 31은 모두 홈 주소 3을 얻는다.

• 분리 체이닝: 3번 버킷의 연결 구조에 10 → 17 → 24 → 31처럼 저장한다.
• 선형 탐사: 3번에 10, 4번에 17, 5번에 24, 6번에 31을 저장한다.

선형 탐사에서 4번의 17을 삭제한 뒤 그 칸을 완전히 빈칸으로 표시하면, 24를 찾을 때 3번의 10 다음 4번에서 탐색을 잘못 종료할 수 있다. 삭제 표시가 필요한 이유다.

적재율과 성능 조건

단순한 한 슬롯당 한 항목 모델에서 적재율은 다음과 같다.

적재율 α = 저장된 항목 수 n ÷ 슬롯 수 m

개방 주소법은 모든 항목이 테이블 내부에 있어야 하므로 α < 1이어야 삽입 가능한 빈 슬롯이 남는다. 체이닝은 한 버킷에 여러 항목을 둘 수 있어 α가 1을 넘을 수 있다. 일반적으로 적재율이 높아질수록 충돌과 탐사 길이 또는 체인 길이가 증가한다.

해시 검색의 평균 Θ(1)은 해시 값이 충분히 고르게 분포하고 적재율이 적절히 관리된다는 전제에서 기대할 수 있다. 많은 키가 같은 버킷이나 긴 탐사열에 몰리면 최악 Θ(n)이 된다. “해싱은 언제나 O(1)”이라는 표현은 조건을 빠뜨린 것이다.

자료구조용 해시는 빠른 저장 위치 계산과 분산이 목적이다. 암호학적 해시는 역상 저항성·충돌 저항성 같은 보안 성질을 목표로 하므로 같은 용도로 취급하지 않는다.

개방 주소법에서 삭제된 칸을 미사용 빈칸과 구분해야 충돌로 뒤에 저장된 키를 계속 찾을 수 있다. 삭제 표시를 사용하거나 후속 클러스터를 올바르게 재구성한다. 삭제 표시만으로 자동 재해싱이 되는 것은 아니다.

테이블 확장과 재해싱에서는 새 크기에 맞춘 해시 함수로 기존 키의 위치도 다시 결정한다. 적재율은 저장 키 수를 버킷 수로 나눈 값이며, 공간을 늘리면 같은 키 수에서 적재율은 낮아진다.

점근 복잡도

입력 경우와 경계 표기는 다른 축

최선·평균·최악은 어떤 입력 경우의 비용을 분석하는지 나타낸다. O·Ω·Θ는 선택된 비용 함수가 다른 함수와 비교해 어떤 점근 경계를 가지는지 나타낸다. 따라서 O = 최악, Ω = 최선, Θ = 평균으로 대응시키면 틀린다.

예를 들어 순차 검색의 최악 비용 함수는 Θ(n)이다. 이 함수는 O(n)이면서 Ω(n)이기도 하다. 또한 3n + 100은 O(n²)라고 해도 수학적으로 틀리지는 않지만, 실제 증가 차수를 가장 정확히 나타내는 밀접한 경계는 Θ(n)이다.

지배항과 반복 구조

입력 크기 n이 커질 때 가장 빠르게 증가하는 항이 전체 증가율을 지배한다.

• 3n² + 5n + 20 → Θ(n²)
• 연속된 두 구간 Θ(n) + Θ(n²) → Θ(n²)
• 각각 n번 도는 독립적인 이중 중첩 반복 → Θ(n²)
• 반복할 때마다 문제 크기를 절반으로 줄임 → Θ(log n)

연속 반복은 비용을 더하고, 중첩 반복은 각 반복 횟수가 독립적으로 전체 범위를 돈다는 전제에서 곱한다. 반복 조건이 서로 의존하거나 매번 범위가 줄어들면 단순히 n을 곱하면 안 된다.

대표 증가 순서는 다음과 같다. 로그의 밑이 1보다 큰 상수라면 밑의 차이는 점근 차수를 바꾸지 않는다.

1 < log n < n < n log n < n² < 2ⁿ < n!

시간·공간·보조 공간

• 시간 복잡도: 비교, 대입, 산술, 디스크 접근 등 정한 기본 연산의 증가율
• 공간 복잡도: 입력 저장 공간을 포함해 알고리즘 실행에 필요한 전체 메모리의 증가율
• 보조 공간(Auxiliary Space): 입력 자체를 제외하고 추가 배열, 임시 버퍼, 재귀 호출 스택 등에 사용하는 공간

따라서 “공간 복잡도는 항상 입력 외의 메모리만 센다”는 설명은 정확하지 않다. 입력을 제외한 추가 메모리만 말할 때는 보조 공간이라고 구분한다. 재귀 알고리즘은 별도 배열을 만들지 않더라도 호출 스택이 보조 공간에 포함될 수 있다.

순차·색인 순차·직접 파일 구조

파일 구조는 접근 경로로 구분한다

여기서 파일은 응용 프로그램이 다루는 레코드 집합이다. 논리 레코드는 고객 한 명이나 거래 한 건처럼 프로그램이 의미 단위로 보는 기록이고, 물리 블록은 저장장치가 한 번의 입출력으로 읽고 쓰는 단위다. 하나의 물리 블록에 여러 논리 레코드가 들어갈 수 있으므로 논리적 순서와 실제 저장 위치를 완전히 같은 것으로 단정하지 않는다.

색인 순차 파일의 세 영역

시험에서 다루는 전형적인 색인 순차 파일은 다음 영역으로 설명한다.

1. 기본 데이터 영역: 키 순서에 따라 레코드를 저장한다.
2. 색인 영역: 키와 데이터 블록의 위치를 연결한다.
3. 오버플로 영역: 기본 영역의 적절한 위치에 바로 넣기 어려운 추가 레코드를 임시로 저장한다.

삽입이 반복되어 오버플로 체인이 길어지면 접근 비용이 커질 수 있으므로, 기본 영역과 색인을 다시 구성하는 재구성 작업이 필요할 수 있다. 색인은 조회를 빠르게 할 수 있지만 저장 공간과 삽입·삭제 시 갱신 비용을 추가한다.

직접 파일과 해시 테이블의 관계

직접 파일은 키로 저장 주소를 계산한다는 점에서 해싱과 원리가 닮았다. 다만 해시 테이블은 주로 메모리 자료구조의 관점에서 슬롯과 탐사열을 설명하고, 직접 파일은 디스크 블록·버킷·오버플로 영역과 입출력 비용을 함께 고려한다. 같은 원리를 사용한다고 두 용어를 완전히 같은 자료구조로 보지는 않는다.

업무 상황에 맞춘 선택

• 모든 고객의 청구서를 고객 번호순으로 매일 출력한다면 순차 파일이 단순하다.
• 고객 번호로 단건 조회하면서 번호순 전체 출력도 필요하면 색인 순차 파일이 균형을 제공한다.
• 주문 번호로 정확히 한 건을 매우 자주 찾고 범위 조회가 거의 없다면 직접 파일이 유리할 수 있다.
• 삽입·삭제가 매우 잦으면 색인 갱신, 오버플로 영역, 재구성 비용까지 비교해야 한다.

어느 구조도 모든 연산에서 항상 우월하지 않다. 동등 검색, 범위 검색, 전체 순차 처리, 삽입·삭제, 저장 공간 중 무엇이 중요한지 먼저 정한다.

검색·해싱·복잡도·파일 구조 한눈에 보기