[CS공부] 3. 검색 알고리즘

악어·2024년 3월 8일
CS검색알고리즘
0

CS / 알고리즘 공부

목록 보기
3/10
post-thumbnail

깃허브 정리본

용어

  • linear search(선형검색) = sequential search(순차검색): 선형으로 늘어선 배열에서 검색하는 경우, 앞부터 순서대로 스캔하는 알고리즘
    => 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법

  • sentinel method(보초법): 선형검색에서 마지막 종료조건(key가 없는경우)에 들어가는 비용을 줄여주는 방법

  • binary search(이진검색): 원소가 오름/내림차순으로 정렬된 배열에서 일종의 업다운 게임 방식으로 scan해야할 범위를 줄여가며 검색하는 방식

  • complexity(복잡도): 알고리즘의 성능을 객관적으로 평가하는 기준

  • time complexity(시간 복잡도): 실행하는 데 필요한 시간 평가

  • space complexity(공간 복잡도): 메모리와 파일 공간이 얼마나 필요한지 평가
    => 표기는 O(n), '오더 n', 'n의 오더'라고 읽음
    => 복잡도의 차원은 높은 곳을 따라감 => O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

  • hashing(해시법): 데이터를 저장할 인덱스를 간단한 연산으로 설정하는 방법. 이를통해 데이터 검색/추가/삭제에 들어가는 비용을 줄임

  • hash value(해시값): 해시법을 실행하기 위해 원래 키값에 간단한 연산을 통해 얻어낸 인덱스

  • hash table(해시테이블): 해시값을 인덱스로하여 원소들을 새롭게 정렬해놓은 배열

  • hash function(해시함수): key를 hash값으로 바꿔주는 함수(로직) => 주로 나머지를 구하는 연산이나 그 응요을 사용함

  • bucket(버킷): 해시 테이블에서 만들어진 원소

  • hash collision(해시충돌): 서로 다른 키의 해시값이 같아 중복되는 현상

  • chaining(체인법)=open hashing(오픈해시법): 해시값이 같은 데이터를 linked list(연결리스트)로 관리하는 방법

  • open addressing(오픈주소법)=closed hashing(닫힌해시법)=linear probing(선형탐사법): 충돌이 발생했을 때 재해시를 통해 빈 버킷을 찾는 방법



실습

선형검색

from typing import Any, Sequence

def sequential_search(arr: Sequence, key: Any) -> int:
    for i in range(len(arr)):
        if arr[i] == key: 
            return i
    else:
        return -1

array = [6, 8, 11, 30, 42, 5, 29, 13]

while True:
    key = int(input("배열에서 찾을 값을 입력해주세요: "))
    index = sequential_search(arr=array, key=key)
    if index == -1: 
        print(f"{key}는 배열 안에 없는 값입니다.") 
    else: 
        print(f"{key}는 배열의 '{index}' 인덱스에 있습니다.")
    x = input("계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): ")
    if x == "y" or x == "Y": continue
    else: break
    

# 실행결과 ==========================================
배열에서 찾을 값을 입력해주세요: 30
30는 배열의 '3' 인덱스에 있습니다.
계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): y
배열에서 찾을 값을 입력해주세요: 29
29는 배열의 '6' 인덱스에 있습니다.
계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): y
배열에서 찾을 값을 입력해주세요: 72
72는 배열 안에 없는 값입니다.
계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): q

보초법

from typing import Any, Sequence
import copy

def sequential_search(arr: Sequence, key: Any) -> int:
    new_arr = copy.deepcopy(arr)
    new_arr.append(key)
    i = 0
    while True:
        if new_arr[i] == key: break
        i += 1
    return -1 if i == len(arr) else i

array = [6, 8, 11, 30, 42, 5, 29, 13]

while True:
    key = int(input("배열에서 찾을 값을 입력해주세요: "))
    index = sequential_search(arr=array, key=key)
    if index == -1: 
        print(f"{key}는 배열 안에 없는 값입니다.") 
    else: 
        print(f"{key}는 배열의 '{index}' 인덱스에 있습니다.")
    x = input("계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): ")
    if x == "y" or x == "Y": continue
    else: break

이진 검색

from typing import Any, Sequence

def binary_search(arr: Sequence, key: Any) -> int:
    pointer_left = 0
    pointer_right = len(arr) - 1
    while True:
        pointer_center = (pointer_left + pointer_right) // 2
        if arr[pointer_center] == key:
            return pointer_center
        elif arr[pointer_center] < key:
            pointer_left = pointer_center + 1
        elif arr[pointer_center] > key:
            pointer_right = pointer_center - 1
        if pointer_left > pointer_right: break
    return -1

array = [6, 8, 11, 30, 42, 58, 69, 71, 90, 98, 105, 107, 129]

while True:
    key = int(input("배열에서 찾을 값을 입력해주세요: "))
    index = binary_search(arr=array, key=key)
    if index == -1: 
        print(f"{key}는 배열 안에 없는 값입니다.") 
    else: 
        print(f"{key}는 배열의 '{index}' 인덱스에 있습니다.")
    x = input("계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): ")
    if x == "y" or x == "Y": continue
    else: break
    

# 실행결과 ==========================================
배열에서 찾을 값을 입력해주세요: 105
105는 배열의 '10' 인덱스에 있습니다.
계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): y
배열에서 찾을 값을 입력해주세요: 8
8는 배열의 '1' 인덱스에 있습니다.
계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): y
배열에서 찾을 값을 입력해주세요: 99
99는 배열 안에 없는 값입니다.
계속 찾으시겠습니까? (y: 계속, 다른 값 입력: 종료): q

해시법: 충돌 시 chainning

from __future__ import annotations
from typing import Any
import hashlib

class Node:

    def __init__(self, key: Any, value: Any, next: Node) -> None:
        self.key = key
        self.value = value
        self.next = next


class ChainedHash:

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.table = [None] * capacity

    def get_hash_value(self, key: Any) -> int:
        if isinstance(key, int): return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity)
    
    def search(self, key: Any) -> Any:
        hash = self.get_hash_value(key)
        node = self.table[hash]
        
        while node is not None:
            if node.key == key: return node.value
            node = node.next

        return None
    
    def add(self, key: Any, value: Any) -> bool:
        hash = self.get_hash_value(key)
        node = self.table[hash]
        
        while node is not None:
            if node.key == key: return False
            node = node.next

        new_node = Node(key, value, self.table[hash])
        self.table[hash] = new_node
        return True
    
    def remove(self, key: Any) -> bool:
        hash = self.get_hash_value(key)
        node = self.table[hash]
        prev_node = None

        while node is not None:
            if node.key == key:
                if prev_node is None:
                    self.table[hash] = node.next
                else: 
                    prev_node.next = node.next
                return True
            prev_node = node
            node = node.next

        return False
    
    def dump(self) -> None:
        for i in range(self.capacity):
            node = self.table[i]
            print(i, end='')
            while node is not None:
                print(f"  -> {node.key} ({node.value})", end='')
                node = node.next
            print()


hash = ChainedHash(13)

while True:
    menu = input("수행할 작업을 선택해주세요\n(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => ")
    if menu == "a" or menu == "A":
        key = int(input("추가할 키를 적어주세요: "))
        value = input("추가할 값을 적어주세요: ")
        if hash.add(key, value): 
            print(f"{key}에 {value}가 추가되었습니다.") 
        else: 
            print("이미 존재하는 값입니다.")
    elif menu == "r" or menu == "R":
        key = int(input("삭제할 키를 적어주세요: "))
        if hash.remove(key): 
            print(f"{key}가 삭제되었습니다.") 
        else: 
            print("테이블에 존재하지 않는 값입니다.")
    elif menu == "s" or menu == "S":
        key = int(input("검색할 키를 적어주세요: "))
        result = hash.search(key)
        if result is not None: 
            print(f"{key}에 해당하는 값은 {result} 입니다.") 
        else: 
            print("해당 키의 값은 테이블에 존재하지 않습니다.")
    elif menu == "d" or menu == "D":
        hash.dump()
    elif menu == "q" or menu == "Q":
        break
    else: 
        continue
        

# 실행결과 ==========================================
(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => r
삭제할 키를 적어주세요: 17
17가 삭제되었습니다.
수행할 작업을 선택해주세요
(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => d
0  -> 26 (39)
1  -> 40 (99)
2  -> 28 (12)
3
4  -> 30 (84)
5  -> 57 (11)  -> 83 (55)  -> 70 (30)
6
7
8  -> 34 (100)
9
10
11  -> 50 (77)
12  -> 38 (26)
수행할 작업을 선택해주세요
(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => s
검색할 키를 적어주세요: 76
해당 키의 값은 테이블에 존재하지 않습니다.
수행할 작업을 선택해주세요
(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => s
검색할 키를 적어주세요: 77
해당 키의 값은 테이블에 존재하지 않습니다.
수행할 작업을 선택해주세요
(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => s
검색할 키를 적어주세요: 50
50에 해당하는 값은 77 입니다.
수행할 작업을 선택해주세요
(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => q

해시법: 충돌 시 rehashing

from __future__ import annotations
from typing import Any
import hashlib
from enum import Enum


class Status(Enum):
    OCCUPIED = 0
    EMPTY = 1
    DELETED = 2


class Bucket:

    def __init__(self, key: Any = None, value: Any = None, status: Status = Status.EMPTY) -> None:
        self.key = key
        self.value = value
        self.status = status
    
    def set(self, key: Any, value: Any, status: Status) -> None:
        self.key = key
        self.value = value
        self.status = status
    
    def set_status(self, status: Status) -> None:
        self.status = status
    

class OpenHash:

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.table = [Bucket()] * capacity

    def get_hash_value(self, key: Any) -> int:
        if isinstance(key, int): return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity)
    
    def get_rehash_value(self, key: Any) -> int:
        return (self.get_hash_value(key) + 1) % self.capacity

    def search_bucket(self, key: Any) -> Any:
        hash = self.get_hash_value(key)
        bucket = self.table[hash]
        
        for _ in range(self.capacity):
            if bucket.status == Status.EMPTY:
                break
            elif bucket.status == Status.OCCUPIED and bucket.key == key:
                return bucket
            hash = self.get_rehash_value(hash)
            bucket = self.table[hash]

        return None

    def search(self, key: Any) -> Any:
        bucket = self.search_bucket(key)
        if bucket is not None:
            return bucket.value
        else:
            return None
    
    def add(self, key: Any, value: Any) -> bool:
        if self.search(key) is not None:
            return False
        
        hash = self.get_hash_value(key)
        bucket = self.table[hash]
        for _ in range(self.capacity):
            if bucket.status == Status.EMPTY or bucket.status == Status.DELETED:
                self.table[hash] = Bucket(key, value, status=Status.OCCUPIED)
                return True
            hash = self.get_rehash_value(hash)
            bucket = self.table[hash]
        return False
    
    def remove(self, key: Any) -> bool:
        bucket = self.search_bucket(key)
        if bucket is None:
            return False
        bucket.set_status(Status.DELETED)
        return True
    
    def dump(self) -> None:
        for i in range(self.capacity):
            bucket = self.table[i]
            print(f"{i:2}. ", end='')
            if bucket.status == Status.OCCUPIED:
                print(f"{bucket.key} ({bucket.value})")
            elif bucket.status == Status.EMPTY:
                print('-- 미등록 --')
            elif bucket.status == Status.DELETED:
                print('-- 삭제 완료 --')

hash = OpenHash(13)

while True:
    menu = input("수행할 작업을 선택해주세요\n(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => ")
    if menu == "a" or menu == "A":
        key = int(input("추가할 키를 적어주세요: "))
        value = input("추가할 값을 적어주세요: ")
        if hash.add(key, value): 
            print(f"{key}에 {value}가 추가되었습니다.") 
        else: 
            print("이미 존재하는 값입니다.")
    elif menu == "r" or menu == "R":
        key = int(input("삭제할 키를 적어주세요: "))
        if hash.remove(key): 
            print(f"{key}가 삭제되었습니다.") 
        else: 
            print("테이블에 존재하지 않는 값입니다.")
    elif menu == "s" or menu == "S":
        key = int(input("검색할 키를 적어주세요: "))
        result = hash.search(key)
        if result is not None: 
            print(f"{key}에 해당하는 값은 {result} 입니다.") 
        else: 
            print("해당 키의 값은 테이블에 존재하지 않습니다.")
    elif menu == "d" or menu == "D":
        hash.dump()
    elif menu == "q" or menu == "Q":
        break
    else: 
        continue
        

# 실행결과 ==========================================
수행할 작업을 선택해주세요
(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => d
 0. -- 미등록 --
 1. 66 (66)
 2. -- 미등록 --
 3. 55 (55)
 4. 17 (17)
 5. 44 (44)
 6. 82 (82)
 7. -- 삭제 완료 --
 8. -- 미등록 --
 9. 22 (22)
10. -- 미등록 --
11. 11 (11)
12. 77 (77)
수행할 작업을 선택해주세요
(a: 추가, r: 제거, s: 검색, d: 덤프, q: 종료) => a
추가할 키를 적어주세요: 19
추가할 값을 적어주세요: 19
19에 19가 추가되었습니다.


정리

'보초법'의 아이디어가 흥미로웠다.

길이가 n인 배열에 대해 선형탐사법을 그냥 실행할 경우
n번의 추가적인 연산이 들어가지만, 보초법의 간단한
아이디어 하나만으로 그 n번의 연산을 하지 않을 수 있었다.

'이진검색'은 마치 업다운 게임을 하는 것 같았는데,
나중에 '이진트리'를 정리하며 더 공부해봐야겠다.

'해시법'은 솔직히 생소한 개념이라 그 필요성에 대해
크게 공감하지 못했는데, 실제로 많은 서비스에서 open addressing을
통해 해시법을 사용하고 있다는 데에 놀랐다.



profile
악어
냅다 회사부터 세워버린 개발자
이전 포스트

[CS공부] 2. 기본 자료구조와 배열

다음 포스트

[CS공부] 4. 스택과 큐

0개의 댓글