검색 알고리즘 - 선형검색, 이진검색, 해시법

검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다.

배열 검색의 종류로는 

 

• 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다.
• 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다.
• 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 
  • 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다.
  • 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다.

---

선형 검색 linear search

가장 기본적인 배열 검색 방법이다. 선형으로 늘어선 배열에서 원하는 Key값을 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘이다.

즉, 선형 검색에서 배열 스캔의 종료 조건은 2가지다.

1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 ... 검색 실패

2. 검색할 값과 같은 원소를 찾는 경우 ... 검색 성공

 

# -- 배열 맨 앞부터 순서대로 원소를 스캔하는 선형 검색은 원소의 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법이다.

 

<code>

 

# -- while 문으로 작성한 선형 검색 알고리즘
# search_while.py 

from typing import Any, Sequence

from sqlalchemy import true

def seq_search(a: Sequence, key: Any):
    i = 0
    
    while True:
        if i == len(a):
            return -1    # 검색에 실패하여 -1을 반환
        
        if a[i] == key:
            return i    # 검색에 성공하여 현재 검사한 배열의 인덱스를 반환
        
        i += 1
        
if __name__ == '__main__':
    num = int(input('Enter the number of elements : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}] : '))
        
    ky = int(input('Enter the Key you want to search for : '))
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('A search Key does not exist.')
    else:
        print(f'The search Key is at x[{idx}].')

 

 

배열의 스캔을 for 문으로 구현하면 코드가 더 짧고 간결해진다. (선형 검색뿐만 아니라 대부분에 적용)

<code>

# -- for 문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence

from sqlalchemy import true

def seq_search(a: Sequence, key: Any):
    for i in range(len(a)):
        if a[i] == key:
            return i    # 검색 성공(인덱스 반환)
    return -1   # 검색 실패(-1 반환)
        
if __name__ == '__main__':
    num = int(input('Enter the number of elements : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}] : '))
        
    ky = int(input('Enter the Key you want to search for : '))
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('A search Key does not exist.')
    else:
        print(f'The search Key is at x[{idx}].')

 

선형 검색은 int 뿐만 아니라 다양한 자료형 검색에 사용할 수 있다.

<open code>

# -- seq_search() 함수를 사용하여 특정 인덱스 검색하기

from search_while import seq_search

t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS', 'AAC', 'FLAC']

print(f'{t}에서 5.6의 인덱스는 {seq_search(t, 5.6)}입니다.')
print(f'{s}에서 "n"의 인덱스는 {seq_search(s, "n")}입니다.')
print(f'{a}에서 "DTS"의 인덱스는 {seq_search(a, "DTS")}입니다.')

 

보초법 sentinel method

선형 검색은 반복할 때마다 두 가지 종료 조건을 체크하는데, 검색 과정을 반복할수록 비용(cost)을 무시할 수 없다. 보초법은 비용을 반으로 줄이는 방법이다.

 

위 사진에서 배열 원소 a[0] ~ a[6]은 기존 데이터이다. 검색하고자 하는 키값을 배열의 끝 a[7]에 저장한다. 저장하는 값을 보초라고 한다. 

그림 b처럼 찾는 값이 존재하지 않아도 선형 검색의 종료 조건 중 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우는 신경 쓰지 않아도 된다.  

 

<code>

# -- while문 선형 검색 알고리즘을 보초법으로 수정

from re import I
from typing import Any, Sequence
import copy

from sympy import sequence

def seq_search(seq: sequence, key: Any):
    a = copy.deepcopy(seq)
    a.append(key)
    
    i = 0
    while True:
        if a[i] == key:
            break   # 검색에 성공하면 while 문 종료
        i += 1
        
    return -1 if i == len(seq) else i    # i값이 len(seq)와 같으면 찾은 것이 보초임으로 실패

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    ky = int(input('검색할 값을 입력하세요 : '))
    
    idx = seq_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
        
    else: 
        print(f'검색값은 x[{idx}]에있습니다.')

---

이진 검색 binary search

이진 검색은 원소가 오름차순이나 내림차순으로 정렬(sort)된 배열에 좀 더 효율적으로 검색할 수 있는 알고리즘이다. (선형 검색보다 빠르게 검색 가능)

위의 그림처럼 오름차순으로 정렬된 배열에서 76을 찾는 과정이다. 이진 검색에서는 배열의 중앙에 위치한 a[7]인 47에 주목한다. 76은 47보다 뒤에 위치한다. 그러면 검색 대상을 a[8] ~ a[14]로 좁힌다. 그다음 중앙값인 a[11]=77과 76을 비교하면 검색 대상을 a[8]~a[10]으로 좁힐 수 있다. 이제 검색해야 하는 대상은 2개고 76의 위치를 찾을 수 있다.

 

검색 범위의 맨 앞(pl), 맨 끝(pr), 중앙(pc)의 인덱스를 각각 0, n-1, (n-1)//2로 초기화한다.

 

<code>

# -- 이진 검색 알고리즘

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any):
    pl = 0
    pr = len(a) - 1
    
    
    while True:
        pc = (pl + pr) // 2 # 중앙원소의 인덱스
        if a[pc] == key:
            return pc   # 검색성공
        
        elif a[pc] < key:
            pl = pc + 1     # 검색 범위 뒤쪽 절반으로 좁힘
        
        else:
            pr = pc - 1
            
        if pl > pr:
            break
    return -1


if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    print('배열 데이터를 오름차순으로 입력하세요 : ')
    
    x[0] = int(input('x[0] : '))
    
    for i in range(1, num):
        while True:
            x[i] = int(input(f'x[{i}]: '))
            if x[i] >= x[i-1]:  # 바로 직전에 입력한 원소값보다 큰 값을 입력
                break
            
    ky = int(input('검색할 값을 입력하세요 : '))
    idx = bin_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

 

이진 검색 알고리즘은 반복할 때마다 검색 범위가 거의 절반으로 줄어들기 때문에 필요한 비교 횟수는 평균 log n이다. 검색에 실패할 경우는 [log(n+1)]번이며, 검색에 성공할 경우는 logn - 1번이다.

---

해시법 hashing

검색과 더불어 데이터의 추가와 삭제도 효율적이다. 해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다.  

배열의 키들은 해시함수를 거쳐서 해시값(Hash Table)을 만들어 낸다. Hash Table은 Index(key)와 value로 이루어져 있으며, 

해시 테이블에서 만들어진 Key값(원소)을 bucket이라고 하고 Value값을 entry라고 한다.

일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 자주 사용한다.

 

만약 유저가 원소 345의 위치를 알고 싶다면 해쉬함수로 나눈 값이 인덱스 넘버이기 때문에 쉽게 위치를 찾을 수 있다.  

 

 

해시 충돌

앞에서 만든 해시 테이블에 135를 추가한다면 100으로 나눈 값은 1이다. 그러나 인덱스 1엔 이미 값(123)이 들어 있다. 키와 해시값의 대응 관계가 꼭 1:1일 필요는 없다. 키와 해시값은 일반적으로 n:1이다. 이처럼 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 한다.  해시법에서 충돌이 발생하는 경우 두 가지 방법으로 대처할 수 있다.

 

• 체인법 : 해시값이 같은 원소를 연결 리스트로 관리
• 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복

만약 충돌이 발생하지 않는다면 해시 함수로 인덱스를 찾는 것만으로 검색-추가-삭제가 가능하기 때문에 시간 복잡도는 O(1)이다. 해시 테이블을 충분히 크게 만들면 충돌을 억제할 수 있지만 메모리를 낭비하게 된다. 즉, 시간과 공간의 trade-off(상충관계)가 발생한다. 충돌을 피하려면 해시 함수가 해시 테이블 크기보다 작거나 같은 정수를 고르게 생성해야 한다. 따라서 해시 테이블의 크기는 소수를 선호한다.

---

 

 

체인법 chaining

체인법이란 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법을 말하며 오픈 해시법이라고도 한다.

배열의 각 버킷(해시 테이블)에 저장하는 것은 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드(head node)를 참조하는 것이다.

위의 그림을 보면 44와 70의 해시값은 둘 다 5이며, 이들을 연결하는 연결 리스트의 앞쪽 노드를  참조하여 table[5]에 저장한다. 참고로 table[2] 처럼 데이터가 하나도 없는 버킷의 값은 None이라고 한다.

 

<open code>

## -- chained_hash.py
from __future__ import annotations
from typing import Any, Type
import hashlib

class Node:
    '''해시를 구성하는 노드
    Node 클래스는 키와 값이 짝을 이루는 구조이다. 키에 해시 함수를 적용하여 해시값을 구한다.'''
    
    def __init__(self, key: Any, value: Any, next: Node):
        '''초기화'''    
        self.key = key  # 키
        self.value = value  # 값
        self.next = next    # 뒤쪽 노드를 참조
        
class ChainedHash:
    '''체인법으로 해시 클래스 구현 
    해시 테이블의 각 버킷은 맨 앞부터 table[0], table[1] 순으로 접근 가능하다
    __init__() 함수가 호출된 직후 배열 table의 모든 원소는 None으로 모두 빈 상태이다.'''    
    
    def __init__(self, capacity: int):
        self.capacity = capacity    # 해시 테이블의 크기 지정
        self.table = [None] * self.capacity     # 해시 테이블(리스트)을 선언
        
    def hash_value(self, key: Any):
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity) # key가 int형이 아닌 경우 형 변환
    
    def search(self, key: Any):
        hash = self.hash_value(key)     # 검색하는 키의 해시값
        p = self.table[hash]            # 노드를 주목
        
        while p is not None:
            if p.key == key:
                return p.value          # 검색 성공
            p = p.next                  # 뒤쪽 노드를 주목
        
        return None                     # 검색 실패
    
    def add(self, key: Any, value: Any):
        hash = self.hash_value(key)     # 추가하는 key의 해시값
        p = self.table[hash]            # 노드를 주목
        
        while p is not None:
            if p.key == key:
                return False            # 추가 실패
            p = p.next                  # 뒤쪽 노드를 주목
            
        temp = Node(key, value, self.table[hash])
        self.table[hash] = temp         # 노드 추가
        return True                     # 추가 성공
    
    def remove(self, key: Any):
        hash = self.hash_value(key)
        p = self.table[hash]
        pp = None
        
        while p is not None:
            if p.key == key:            # 키를 발견하면 아래의 코드 실행
                if pp is None:
                    self.table[hash] = p.next
                else:
                    pp.next = p.next         
                return True             # 키 삭제 성공
            pp = p
            p = p.next                  # 뒤쪽 노드를 주목
        return False                    # 삭제 실패(key가 존재하지 않음)
    
    def dump(self):    # -- 원소를 출력하는 함수
        for i in range(self.capacity):
            p = self.table[i]
            print(i, end='')
            while p in not None:
                print(f'  -> {p.key} ({p.value})', end='')
                p = p.next
            print()

from enum import Enum
from os import sep
from chained_hash import ChainedHash

Menu = Enum('Menu', ['추가', '삭제', '검색', '덤프', '종료']) # 메뉴 선언

def select_menu():
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep='  ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
hash = ChainedHash(13)

while True:
    menu = select_menu()
    
    if menu == Menu.추가:
        key = int(input('추가할 키를 입력하세요 : '))
        val = input('추가할 값을 입력하세요 : ')
        if not hash.add(key, val):
            print('추가를 실패했스니다.')
            
    elif menu == Menu.삭제:
        key = int(input('삭제할 키를 입력하세요 : '))
        if not hash.remove(key):
            print('삭제를 실패했습니다.')
    
    elif menu == Menu.검색:
        key = int(input('검색할 키를 입력하세요 : '))
        t = hash.search(key)
        if t is not None:
            print(f'검색한 키를 갖는 값은 {t}입니다.')
        else:
            print('검색할 데이터가 없습니다.')
    elif menu == Menu.덤프:
        hash.dump()
        
    else:
        break

 

 

오픈 주소법 open addressing

오픈 주소법은 충돌이 발생했을 때 재해시를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법이라고도 한다.

오픈 주소법은 빈 버킷이 나올 때까지 재해시를 반복하므로 선형 탐사법(linear probing)이라고도 한다.

 

 

원소 삭제하기

위 그림의 배열에서 5를 삭제하고 싶다면 인덱스가 5인 버킷을 비우기만 하면 될 것 같지만, 해시값이 같은 18을 검색할 때 해시값이 5인 데이터는 존재하지 않는다고 착각하여 검색에 실패한다. 그렇기 때문에 버킷의 상태를 비어 있는 상태(-)와 삭제 완료된 상태(*)로 나타낸다.

원소 검색하기

17을 검색한다고 가정하면 해시값이 4인 버킷은 비어 있는 상태 이므로 검색에 실패한다. 18을 검색한다면 해시값인 5인 버킷은 삭제 완료 상태이다. 그래서 재해시를 반복하여 5 -> 6 -> 7 순으로 버킷 값을 옮겨서 검색하는 값을 찾아낼 수 있다.

 

<open code>

# -- open_hash.py
from  __future__ import annotations
from telnetlib import STATUS
from typing import Any, Type
from enum import Enum
import hashlib

class Status(Enum):
    OCCUPIED = 0   # 데이터를 저장
    EMPTY = 1      # 비어 있음
    DELETE = 2     # 삭제 완료
    
class Bucket:
    '''해시를 구성하는 버킷'''
    def __init__(self, key: Any = None, value: Any = None, stat: Status = Status.EMPTY):
        self.key = key
        self.value = value
        self.stat = stat
        
    def set_satus(self, stat: Status):
        '''속성을 설정'''
        self.stat = stat
        
class OpenHash:
    '''오픈 주소법으로 구현하는 해시 클래스'''
    def __init__(self, capacity: int):
        '''초기화'''
        self.capacity = capacity                  # 해시 테이블의 크기를 지정
        self.table = [Bucket()] * self.capacity   # 해시 테이블
        
    def hash_value(self, key: Any):
        '''해시값을 구함'''
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.md5(str(key).encode()).hexdigest(), 16) % self.capacity)
    
    def rehash_value(self, key: Any):
        '''재해시값을 구함'''
        return(self.hash_value(key) + 1) % self.capacity
    
    def search_node(self, key):
        '''키가 key인 버킷을 검색'''
        hash = self.hash_value(key) # 검색하는 키의 해시값
        p = self.table[hash]        # 버킷을 주목
        
        for i in range(self.capacity):
            if p.stat == Status.EMPTY:
                break
            elif p.stat == Status.OCCUPIED and p.key == key:
                return p
            hash = self.rehash_value(hash)    # 재해시
            p = self.table[hash]
        return None
    
    def search(self, key):
        p = self.search_node(key)
        if p is not None:
            return p.value
        else:
            return None
        
    def add(self, key, value):
        '''키가 key이고 값이 value인 원소를 추가'''
        if self.search(key) is not None:
            return False    # 이미 등록된 키
        
        hash = self.hash_value(key)  # 추가하는 키의 해시값 
        p = self.table[hash]         # 버킷을 주목
        for i in range(self.capacity):
            if p.stat == Status.EMPTY or p.stat == Status.DELETE:
                self.table[hash] = Bucket(key, value, Status.OCCUPIED)
                return True
            hash = self.rehash_value(hash)    # 재해시
            p = self.table[hash]
        return False
    
    def remove(self, key):
        p = self.search_node(key)
        if p is None:
            return False
        p.set_satus(Status.DELETE) # -- ? 다른 클래스 아닌가?
        return True
    
    def dump(self):
        for i in range(self.capacity):
            print(f'{i:2}', end='')
            if self.table[i].stat == Status.OCCUPIED:
                print(f'{self.table[i].key} ({self.table[i].value})')
            elif self.table[i].stat == Status.EMPTY:
                print('-- 미등록 --')
            elif self.table[i].stat == Status.DELETE:
                print('-- 삭제 완료 --')

from enum import Enum
from os import sep
from open_hash import OpenHash

Menu = Enum('Menu', ['추가', '삭제', '검색', '덤프', '종료']) #메뉴를 선언

def select_menu():
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep= ' ', end='')
        n = int(input(": "))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
hash = OpenHash(13)

while True:
    menu = select_menu()
    
    if menu == Menu.추가:
        key = int(input('추가할 키를 입력하세요 : '))
        val = input('추가할 값을 입력하세요 : ')
        if not hash.add(key, val):
            print('추가를 실패했습니다.')
            
    elif menu == Menu.삭제:
        key = int(input('삭제할 키를 입력하세요 : '))
        if not hash.remove(key):
            print('삭제를 실패했습니다.')
    
    elif menu == Menu.검색:
        key = int(input('검색할 키를 입력하세요 : '))
        t = hash.search(key)
        if t is not None:
            print(f'검색한 키를 갖는 값은 {t}입니다.')
        else:
            print('검색할 데이터가 없습니다.')
            
    elif menu == Menu.덤프:
        hash.dump()
        
    else:
        break