[Algorithm] 검색 알고리즘

이진 검색

이진 검색:원소가 오름차순이나 내림차순으로 정렬된 배열에서 사용
ex) 5 7 15 28 29 31 39 58 68 70 95에서 39찾기
39는 중간 값 31 보다 큼
-> 31 뒤 부터 검색
39 58 68 70 95
39는 중간 값 68보다 작음
-> 68 앞 부터 검색
39 58
39는 중앙 값 39와 일치 -> 검색 성공

검색 범위의 맨 앞,맨 뒤,중앙 -> pl,pr,pc
pl = 0,pr = n - 1,pc = (n-1)//2로 초기화
list[pc]와 key값을 비교

1.a[pc] < key일 때
검색 범위는 a[pc + 1]~a[pr]로 좁혀짐,pl = pc + 1로 업데이트
2.a[pc] > key일 때
검색 범위는 a[pl]~a[pc - 1]로 좁혀짐,pr = pc = 1로 업데이트
pr > pl이 되면 검색 실패

이진 검색 복잡도

반복할 때마다 검색 범위가 거의 절반 씩 줄어들음
필요한 비교 횟수 평균 log(n)
검색에 실패할 경우는 log(n+1)
검색에 성공할 경우는 log(n-1)

*시간 복잡도(time complexcity):실행하는 데 필요한 시간을 평가
*공간 복잡도(space complexity):메모리(기억 공간)와 파일 공간이 얼마나 필요한지를 평가

해시법

해시법은 검색 뿐만 아니라 데이터의 추가,삭제도 효율적으로 수행 가능
'데이터를 저장할 위치 = 인덱스' 를 간단한 연산으로 구함.
해시값(hash value) : 키(배열 값) % 원소 개수
해시 테이블(hash table) : 해시값 새로 저장한 배열
ex) 원소 값이 14면 x[1]에 저장
해시 함수(hash function) : 키를 해시값으로 변환
버킷(bucket) : 해시 테이블에서 만들어진 원소

해시 충돌

키와 해시값의 대응 관계과 n:1이 될 때 , 즉 버킷이 중복되는 현상을 충돌(collision)이라고 한다.
ex) 18 % 13 했는데 x[5]에 버킷이 이미 있음

이때 두 가지 방법으로 대처 가능

체인법

체인법: 해시값이 같은 원소를 연결 리스트로 관리,오픈 해시법이라고도 한다.

노드

해시 테이블
* int(,16)은 16진수로 만들어줌. 사실 default가 10임.hex()랑 똑같음

검색,추가 기능 구현

삭제,덤프 기능 구현

*덤프: 전부 보여주는거
연결 리스트에서 보통 위치를 저장해서 연결하는데 이건 next에 객체 자체를 넣어서 낯설었다...ㅜ

*Enum은 열거형(Enumerated Type)이라고 부름. 해당 언어의 상수 역할을 하는 식별자로, 일부 열거자 자료형은 언어에 기본으로 포함되어 있음. 그 대표적인 예가 Boolean 자료형으로 False, True 값이 미리 정의된 열거형으로 볼 수 있다.대부분의
ex) False == 0, True == 1

응용해보았다.

오픈 주소법

해시 충돌이 발생했을 때 재해시(rehashing)을 수행하여 빈 버킷을 찾음.
닫힌 해시법(closed hashing)이라고도 한다.

다음은 오픈 주소법을 이용한 것

from future import annotations
from typing import Any, Type
from enum import Enum
import hashlib

class Status(Enum):
OCCUPIED = 0 # 데이터를 저장
EMPTY = 1 # 비어 있음
DELETED = 2 # 삭제 완료

class Bucket:

# 해시를 구성하는 버킷

def __init__(self, key: Any = None, value: Any = None, stat: Status = Status.EMPTY):
    # ex) key의 자료형은 Any라고 어노테이션 해주고 값은 None이다.init함수니까 값을 넣어준거
    self.key = key # 키
    self.value = value # 값
    self.stat = stat # 속성

def set(self, key: Any, value: Any, stat: Status) -> None:
    # 모든필드에 값 설정
    self.key = key # 키
    self.value = value # 값
    self.stat = stat # 속성

def set_status(self, stat: Status) -> None:
    # 속성을 설정
    self.stat = stat

class OpenHash:

# 오픈 주소법으로 구현하는 해시 클래스

def __init__(self, capacity: int) -> None:
    # 초기화
    self.capacity = capacity # 해시 테이블의 크기를 지정
    self.table = [Bucket()] * self.capacity # 해시 테이블

def hash_value(self, key: Any) -> int:
    # 해시 값 구하기
    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) -> int:
    # 재해시
    return((self.hash_value(key) + 1) % self.capacity)
    # 여기선 튀어나온 해시값에 1을 더해주는거지 원래 key값에 더하는게 아님

def search_node(self, key: Any) -> Any:
    # 검색
    hash = self.hash_value(key)
    p = self.table[hash]

    for i in range (self.capacity):
        if p.stat == Status.OCCUPIED and p.key == key:
            return p
        elif p.stat == Status.EMPTY:
            return None
        hash = self.rehash_value(hash) # 재해시
        p = self.table[hash]
    return False # 해시 테이블이 가득 참

def search(self, key: Any) -> Any:
    #같은 키의 원소를 검색하여 값을 반환,그냥 search_node에서 p 받아와서 p.value 뱉음
    p = self.search_node(key)
    if p is not None:
        return p.value
    else:
        return None

def add(self, key: Any, value: Any) -> bool:
    if self.search(key) is not None:
        return False

    hash = self.hash_value(key) # 추가하는 키의 해시값
    p = self.table[hash]

    for i in range (len(self.capacity)):
        if p.stat == Status.EMPTY or p.stat == Status.DELETED:
            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: Any) -> bool:
    p = self.search_node(key)

    if p is None:
        return False
    p.set_status(Status.DELETED)
    # 파이썬 변수 선언은 값 복사가 아니라 바인딩이라...? 잘 모르겠음 ㅠ
    return True
    
    ....
    
    이것도 만들어 보았다.