[자료구조] 탐색

 

1. 탐색

(1) 탐색의 기본 정의

- 탐색 : 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업

- 테이블 : 레코드들의 집합

- 탐색키 : 레코드들이 서로를 구별하여 인식할 수 있는 키

- 엔트리 : 키/값으로 구성된 필드

- 키 :영어 단어나 사람 이름과 같은 레코드의 구분이 가능한 탐색키

- 값 : 영어 단어 의미나 사람 주소같은 탐색키와 관련된 값

- 맵 또는 딕셔너리 : 엔트리로 불리는 키를 가진 레코드 집합 (탐색을 위한 자료구조)

 > 자료를 저장하고 탐색키를 이용해 원하는 자료를 빠르게 찾도록 함

(2) 파이썬의 자료구조

- 내장자료형 딕셔너리 제공-자료 구조 맵 구현 예

- 맵 : 키-값의 쌍으로 이루어진 엔트리 집합

(3) MAP ADP 

- 데이터 : 키를 가진 레코드(엔트리) 집합

- 연산 : search(key) 탐색키 키를 가진 레코드를 찾아 반환

            insert(entry) 주어진 엔트리를 맵에 삽입

            delete(key) 탐색키 키를 가진 레코드를 찾아 삭제

> 맵은 유일한 탐색키를 사용하기도 하고, 동일한 탐색키 중복을 허용하기도 함

- 리스트 : 가장 간단, 엔트리를 키에 따라 정렬하여 맵을 구성하거나 정렬하지 않고도 맵 구성 가능, 방법에 따라 연산 성능차이 발생

- 이진 탐색 트리 : 탐색 성능 향상 가능

- 해쉬 탐색 :  

(4) 간단한 탐색 알고리즘

- 알고리즘 공통 매개변수 : 탐색 대상 리스트 A,  탐색키 key, 리스트 내 탐색 범위 low, high

ⓐ 순차 탐색

- 가장 단순하고 직관적

- 테이블의 각 레코드를 처음부터 하나씩 순서대로 검사하여 원하는 레코드를 검사

- 리스크 low 위치부터 탐색 시작

- 탐색키 key 탐색 성공 시 해당 위치 반환

- 리스트 high 위치까지 가도 원하는 레코드가 없으면 None 반환

def s(A, key, low, high) :     for i in range(low, high+1) :         if A[i].key == key :             return i     return None

- 최선의 경우 1, 최악의 경우 n번, 평균 횟수 n+1/2, 시간복잡도 : O(n)

ⓑ 이진탐색

- 테이블이 키 값으로 정렬되었을 때 개선된 탐색

- 테이블의 중앙값을 조사하고, 찾는 항목이 왼쪽인지 오른쪽인지 판단

- 매 단계마다 검색항목이 반씩 줄어듦

- 예시 : 사전에서 단어찾기

- low~high의 중간값 mid 계산 > 탐색 위치의 mid 기준 반환 > low = mid+1 (or high=mid-1)로 설정하고 다시 1 반복

 > 찾는 값이 없으면 반복 결과 low가 high보다 커질 때 None 반환

- 탐색 범위가 1이 될때까지 반복된 탐색 횟수를 k라 하면 2^k=n이므로 

- 양변에 log2를 씌우면 탐색 횟수 log(2)n, O(k) = O(log(2)n)

- 단점 : 반드시 정렬되어 있어야 함, 자료 삽입/삭제가 빈번한 경우 적합하지 않음(정렬해야 하기 때문에)

ⓒ 보간 탐색

- 이진 탐색의 일종으로 탐색키가 존재할 위치를 예측하여 탐색

- low, high 위치 고려하여 불균등 분할 (이진 탐색은 반으로 분할)

- 테이블 키 값으로 정렬되어 있을 때 개선된 탐색

- low~high는 탐색 범위 최소, 최대 인덱스를 정의 > 탐색 위치 mid = low + (high-low) [ k -A[low]]/[A[high]-A[low]]

 > low =mid+1 (high=mid-1)로 설정하고 처음부터 반복

 > 찾는 값이 없으면 반복 결과 low가 high보다 커지며 그 때 None 반환

- 시간 복잡도는 최악의 경우를 고려하여 이진탐색과 동일한 O(logn)

- 데이터가 비교적 균등 분포되어있는 경우는 이진 탐색보다 훨씬 효과적임

[ 실습 ]

import sys input = sys.stdin.readline def sequential_search(A, key, low, high) :     for i in range(low, high+1) :         if A[i].key==key :             return i     return None def binary_search(A, key, low, high) :     if (low<=high) :         mid = (low+high)//2         if key == A[mid].key :             return mid         elif (key<A[mid].key) :             return binary_search(A, key, low, mid-1)         else :             return binary_search(A, key, mid+1, high)     return None def binary_search_iter(A, key, low, high) :     while(low<=high) :         mid = (low+high) //2         if key == A[mid].key :             return mid         elif key > A[mid].key :             low = mid +1         else :             high = mid-1     return None class Entry :     def __init__ (self, key, value) :         self.key = key         self.value = value     def __str__ (self) :         return str("%s%s"%(self.key, self.value)) class Sequential_Map :     def __init__ (self) :         self.table = []     def size (self) :         return len(self.table)     def display (self, msg) :         print(msg)         for entry in self.table :             print(" ", entry)     def insert (self, key, value) :         self.table.append(Entry(key, value))     def search (self, key) :         pos = sequential_search(self.table, key, 0, self.size()-1 )         #pos = binary_search(self.table, key, 0, self.size()-1 )         #pos = binary_search_iter(self.table, key, 0, self.size()-1 )         if pos is not None : return self.table[pos]         else : return None     def delete (self, key) :         for i in range(self.size()) :             if self.table[i].key == key :                 self.table.pop(i)                 return map = Sequential_Map() map.insert('b','비') map.insert('a','에이') map.insert('c','씨') map.insert('d','디') map.display("나의 단어장 : ") print("탐색:a -->", map.search('a')) print("탐색:b -->", map.search('b')) print("탐색:c -->", map.search('c')) map.delete('c') map.display("나의 단어장 : ")

나의 단어장 :    b비   a에이   c씨   d디 탐색:a --> a에이 탐색:b --> b비 탐색:c --> c씨 나의 단어장 :    b비   a에이   d디

2. 해상과 오버플로

(1) 해싱의 개념

- 기존 탐색처럼 탐색키와 레코드의 키값을 비교하는 것이 아니라, 키값에서 산술적인 연산을 적용하여 레코드 저장되어 있는 위치로 바로 감

- 해시함수 : 키값으로부터 레코드 저장 위치를 계산하는 함수

- 해시 테이블 : 해시 함수에 의해 계산된 위치에 레코드를 저장한 테이블

- 탐색키가 1~1000사이의 정수 일 시 1000개의 항목을 가지는 배열을 만들고 탐색키를 인덱스로 저장

- 해시함수는 h(key)=key로 이상적인 연산속도 O(1)

- 단, 큰 메모리 필요

- 메모리가 부족한 경우 : 탐색키를 직접 인덱스로 사용하지 않고, 탐색키를 정수로 대응시키는 해시 함수 필요

- 해시 함수는 탐색키로 해시 주소를 계산

- 삽입, 삭제, 탐색 연산은 이 해시 주소로 이루어짐

- 해시테이블 : M개의 버킷으로 구성, 하나의 버킷은 여러개의 슬롯으로 구성

- 충돌 : 서로 다른 키가 해시함수에 의해 같은 주소로 계산되는 경우

- 동의어 : 충돌을 일으키는 키들

- 오버플로 : 충돌 발생 시 버킷에 여러개의 슬롯이 있다면 서로 다른 슬롯에 저장하여 충돌 방지가 가능하나, 충돌이 슬롯수보다 많이 발생하면 버킷에 더 이상 저장 불가 == 오버 플로 발생

- 오버플로로 인한 해시 성능 저하

 > 메모리 효율을 위해 해싱 테이블의 크기를 줄이고, 해시 함수를 이용

 > 충돌과 오버플로가 빈번하게 발생하여 시간 복잡도가 O(1)보다 저하됨

(2) 오버플로 처리

- 충돌이 일어나면 해시 테이블의 다음 위치에 저장

- 다음 항목을 순서대로 조사 : h(k), h(k)+1, ...

- 빈곳이 있으면 저장 > 군집화 현상 (옆으로 꽉차는 부분만 데이터가 무리지어 있는 현상)

- 레코드를 찾거나 레코드가 없는 버킷을 만나거나, 모든 버킷을 다 검사할 때까지 진행

- 빈 버킷을 두가지로 나뉨 : 한번도 사용하지 않은 것, 사용했다 지워진 것

[ 선형 조사 군집화 완화 방법 삭제 ]

- 이차 조사법 : 충돌이 발생하면 다음 조사 위치를 바로 충돌 발생 위치 다음이 아니라 다음 식에 의해 결정

  (h(k)+i*i)%M for i =0 to M-1

- 이중 해싱법 : 재해싱, 충돌이 발생하면 다른 해시 함수를 이용해 다음 조사 위치 계산

- 채이닝에 의한 오버플로 처리 : 하나의 버킷에 여러 개의 레코드를 저장 (슬롯의 개념)

  > 필요한 메모리만 사용하여 공간 효율 우수, 오버플로 발생 시 해당 버킷 연결 리스트만 처리하므로 시간 효율 우수

- 좋은 해시 함수 조건 : 충돌이 적음, 주소가 테이블에 고르게 분포, 계산이 빠름

- 제산 함수(M은 소수 사용), 폴딩 함수(XOR), 중간 제곱 함수, 비트 추출(2^k), 숫자 분석, 탐색키가 문자열 

탐색 방법		탐색	삽입	삭제
순차 탐색		O(n)	O(1)	O(n)
이진 탐색		O(log(2)n)	O(n)	O(n)
이진 탐색 트리	균형 트리	O(log(2)n)	O(log(2)n)	O(log(2)n)
	경사 트리	O(n)	O(n)	O(n)
해싱	최선	O(1)	O(1)	O(1)
	최악	O(n)	O(n)	O(n)

- 해싱의 적재 밀도(적재 비율) : a = 저장된 항목 개수 n / 해시 테이블 버킷의 개수 M

(3) 단어장 예제

import sys input = sys.stdin.readline class Entry :     def __init__ (self, key, value) :         self.key = key         self.value = value     def __str__ (self) :         return str("%s%s"%(self.key, self.value)) class Node :     def __init__ (self, data, link=None) :         self.data = data         self.link = link          class Hashchain_Map :     def __init__ (self, M) :         self.table = [None] * M         self.M = M     def hashFn(self, key) :         sum = 0         for n in key :             sum = sum + ord(n)         return sum % self.M     def insert (self, key, value) :         idx = self.hashFn(key)         self.table[idx] = Node(Entry(key, value), self.table[idx])          def search (self, key) :         idx = self.hashFn(key)         node = self.table[idx]         while node is not None :             if node.data.key == key :                 return node.data             node = node.link         return None          def delete (self, key) :         idx = self.hashFn(key)         node = self.table[idx]         before = None         while node is not None :             if node.data.key == key :                 if before == None :                     self.table[idx] = node.link                 else :                     before.link = node.link                 return             before = node             node = node.link                  def display (self, msg) :         print(msg)         for idx in range(len(self.table)) :             node = self.table[idx]             if node is not None :                 print("[%2d] -> "%idx, end = ' ')                 while node is not None :                     print(node.data, end='->')                     node = node.link                 print() map = Hashchain_Map(13) map.insert('b','비') map.insert('a','에이') map.insert('c','씨') map.insert('d','디') map.display("나의 단어장 : ") print("탐색:a -->", map.search('a')) print("탐색:b -->", map.search('b')) print("탐색:c -->", map.search('c')) map.delete('c') map.display("나의 단어장 : ")

나의 단어장 :  [ 6] ->  a에이-> [ 7] ->  b비-> [ 8] ->  c씨-> [ 9] ->  d디-> 탐색:a --> a에이 탐색:b --> b비 탐색:c --> c씨 나의 단어장 :  [ 6] ->  a에이-> [ 7] ->  b비-> [ 9] ->  d디->