Archive

10_Search

9 min read

  • 탐색

    • 테이블(레코드의 집합)에서 원하는 탐색키를 가진 레코드를 찾는 작업

  • 테이블 구성 방법

    • 배열, BST, 해시 테이블 등
    • → 테이블 구조에 따라 탐색·삽입·삭제 성능이 달라짐

2.1. Definition

  • Comparison-based Search

    • 찾고자 하는 키(Key) 값을 데이터 구조 내의 다른 원소들과 직접 비교(대소 관계 또는 일치 여부)해가며 대상의 위치를 찾아내는 방식이다.

  • 탐색 원리

    • 원소들을 순차적으로 비교하거나,
    • 데이터를 특정 기준(예: 크기순 정렬)으로 나누어 가며 비교 범위를 좁혀 나간다.

  • 대표적인 알고리즘 및 자료구조

    • 순차 탐색 (Linear Search): 처음부터 끝까지 하나씩 비교 ()
    • 이진 탐색 (Binary Search): 정렬된 데이터에서 중간값과 비교하여 탐색 범위를 절반씩 줄임 ()
    • 이진 탐색 트리 (Binary Search Tree, BST): 부모 노드를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값을 배치하여 탐색 ()

2.2. Features

  • 장점

    • 데이터의 정렬 상태가 유지되므로 범위 검색(Range Query, 예: 10 이상 50 이하인 값 찾기)이나 최대/최소값 탐색, 정렬된 순서로 순회하는 작업이 수월하다.

  • 단점

    • 데이터의 양 이 늘어날수록 비교 횟수도 함께 증가하므로, 데이터가 매우 많을 때는 해시 기반 탐색보다 속도가 느리다.

  • 순차 탐색(선형 탐색)

    • 일렬로 늘어선 레코드를 앞에서부터 순차적으로 비교하며 탐색
    • 배열이나 연결 리스트로 구성

  • 동작

    • 배열의 left부터 right까지 순서대로 탐색키와 비교
    • 같으면 성공(인덱스 반환), 끝까지 없으면 실패(-1 반환)
    • 시간 복잡도: 최선 O(1), 평균/최악 O(n)
    • 분석: 비효율적이지만, 비정렬 테이블이라면 별다른 대안은 없음
for (int i = left; i <= right; i++)
	if (A[i] == key) {
		// if (i != left) { i -= int; swap(A[i], A[i+1])} // 교환 전략
		return i;
	]
return -1;
  • 개선 - 자기 구성 순차 탐색

    • 자주 탐색되는 레코드를 테이블의 앞쪽으로 옮겨 탐색 효율 증가

    • move to front: 찾은 레코드를 맨 앞으로 이동

    • transpose: 찾은 레코드를 한 칸씩 앞쪽으로 교환

    • count-based: 탐색 횟수 집계 후 빈도 순으로 재배치

int binary_search(int A[]. int key, int low, int high) {
	while (low <= high) {
		int mid = (low + high) / 2;
		if (key == A[mid]) return mid; // 탐색키와 레코드가 같으면 반환
		else if (key < A[mid]) high = mid - 1; // 레코드가 크면 왼쪽으로
		else low = mid + 1; // 레코드가 작으면 오른쪽으로
	}
	return -1;
}

  • 이진 탐색

    • 정렬된 배열에서 중앙값 요소와 비교하여 탐색 범위를 절반씩 줄여 나가는 방법

  • 분석

    • 삽입/삭제: O(n), 탐색: O(log n) (매 단계마다 범위를 절반으로 축소)
    • 삽입/삭제가 빈번하면 AVL 트리
    • 탐색 연산만 주로 처리하면 효율적

  • 메모

    • 분할 정복 알고리즘: 큰 문제를 작은 문제로 나누어서 해결
    • 표현: 이진 탐색 트리의 깊이(depth)

  • 보간 탐색(Interpolation Search)
    • 탐색키가 존재할 위치를 예측하여 탐색하는 방법
    • 래코드의 키값과 탐색키의 비율을 고려해 탐색 위치 계산

  • Hash-based Search

    • 데이터를 비교하는 과정 없이, 키(Key) 값을 해시 함수에 입력하여 데이터가 저장된 메모리 주소(인덱스)를 즉시 계산해 직접 접근하는 방식이다.

  • 탐색 원리

    1. 키를 해시 함수에 통과시켜 고유한 주소값을 얻는다. (키 → [해시 함수] → 해시 주소)
    2. 그 주소에 해당하는 해시 테이블(Hash Table)의 슬롯에서 데이터를 바로 가져온다. (해시 주소 → [해시 테이블](버킷×슬롯))

  • 대표적인 자료구조

    • 해시 테이블(Hash Table)
    • 해시 맵(Hash Map)
    • 해시 셋(Hash Set)

3.1. Definition

  • Hashing

    • 임의의 크기를 가진 데이터를 고정된 크기의 해시값으로 변환하는 기술
    • 해시 함수(Hash Function)를 사용하여 입력 데이터를 계산하고, 결과값을 해시 테이블에 저장하거나 조회한다.

  • 좋은 해시 함수

    • 빠른 계산
    • 고르게 분포
    • 적은 충돌

  • 해시 함수의 종류

    • 제산(나누기→소수) 함수
    • 폴딩 함수
    • 중간 제곱 함수
    • 비트 추출 방법
    • 숫자 분석 방법

3.2. Features

  • Time Complexity

    • Best:
    • Average: (데이터의 개수와 상관없이 거의 일정한 시간 내에 탐색 가능)
    • Worst: (모든 키에 같은 해시 주소 매핑)

  • 장점

    • 대용량 데이터에서도 키-값 쌍을 매우 빠르게 찾을 수 있어 성능 면에서 유리하다.

  • 단점

    • 데이터가 저장되는 순서가 보장되지 않아 순서 있는 정렬이나 범위 탐색이 불가능하다.
    • 해시 테이블의 효율을 유지하기 위해 일정 수준 이상의 메모리 공간을 미리 비워두어야 하므로 공간 효율성이 낮을 수 있다.
    • 해시 충돌(Hash Collision) 또는 동의어(Synonym) → 해시 오버플로(Overflow; 충돌이 슬롯 공간을 초과하는 상황)
      • 서로 다른 키가 동일한 주소값으로 계산되는 상황이다.
      • 충돌이 잦아질 경우 최악의 경우 시간 복잡도가 으로 저하될 수 있다.

3.3. 충돌 처리

(1) 개방 주소법

  • 개방 주소법(open addressing)

    • 선형 조사(linear probing): h(k), h(k)+1, …

  • + 클러스터링 완화

    • 이차 조사(quadratic probing): h(k)+1², +2²,…
    • 이중 해싱(double hashing): 두 번째 해시 함수 이용

(2) 체이닝(Chaining)

  • 체이닝(Chaining)
    • 동일 해시 주소에 여러 데이터를 연결 리스트로 저장

3.4 Applications

  • 데이터 검색, 암호화, 데이터 무결성, 부하 분산, 캐싱, 블록체인
  • 암호학적 해시는 충돌과 역추적이 불가능하고 입력 변화에 민감한 것이 핵심이다.

그래프 뷰

백링크