[구버전] [Python] 02. 검색 알고리즘

📌 검색 알고리즘이란?

📚 검색의 종류

1. 배열 검색 (선형 검색)
2. 연결 리스트 검색
3. 이진 검색 트리 검색

 

📚 배열 검색 중에 배울 내용

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

 

📌 선형 검색

📚 선형 검색 (linear search) / 순차 검색

• 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우 사용
• 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘
• 배열의 개수가 n이라면 이 조건을 판단하는 횟수는 평균 n/2번
• 원소의 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법

 

📚 선형검색

i = 0
while True:
	if i == len(a):
		# 검색 실패
	if a[i] == key:
		# 검색 성공(찾은 원소의 인덱스는 i)
	i += 1

from typing import Any, Sequence

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

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}]에 있습니다.')

 

📚 보초법

• 보초법 : 종료 조건을 검사하는 비용을 반으로 줄이는 방법
• 검색할 값을 배열의 맨 마지막에 저장함, 이 저장하는 값을 보초(sentinel)라고 함
• 이렇게 하면 검색 실패를 판단할 필요가 없음 / 종료조건이 필요 없음

from typing import Any, Sequence
import copy

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

• a 마지막에 보초인 key를 추가
• 배열의 원소를 스캔하며 검색
• 찾은 원소가 배열의 보초인지 판단이 필요
• 보초법을 이용하여 if문의 판단횟수는 반으로 줄이지만, 반환값을 위해 1회는 늘어남

 

📌 이진 검색

📚 이진 검색 (binary search)

• 배열의 데이터가 정렬되어 있다면 선형 검색보다 빠르게 검색
• 정수의 나눗셈은 소수점 이하를 버리므로 중앙값이 연산됨
• 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 반으로 좁혀짐
• 이진 검색에서는 주목할 원소를 다음에 검색할 범위의 중간 지점으로 단숨에 이동

 

📚 이진 검색 수도 코드

• a[mid] < key : 중앙에서 오른쪽으로 한 칸 이동하여 새로운 왼쪽 끝으로 지정, 검색 범위를 뒤쪽 절반으로 좁힘
• a[mid] > key : 중앙에서 왼쪽으로 한 칸 이동하여 새로운 오른쪽 끝으로 지정, 검색 범위를 앞쪽 절반으로 좁힘
• key 값이 일치하거나, 검색 범위가 없으면 종료

from typing import Any, Sequence

def binary_search(a: Sequence, key: Any) -> int:
    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 = binary_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 없습니다.')
    else:
        print(f'검색값은 x[{i}]에 있습니다.')

• 검색 알고리즘은 검색 범위가 절반으로 줄어듦
• 검색에 필요한 비교 횟수는 평균 log n
• 검색에 실패한 경우 [log(n+1)], 검색에 성공한 경우 log n - 1

 

📌 복잡도

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러등의 조건

 

📚 복잡도

• 알고리즘의 성능을 객관저그올 평가하는 기준
• 시간 복잡도(time compolexity) : 실행하는데 필요한 시간을 평가
• 공간 복잡도(space complexity) : 메모리(기억공간)와 파일 공간이 얼마나 필요한지를 평가

 

📚 선형 검색의 시간 복잡도

# 실행횟수 | 복잡도
def seq_search(a: Sequence, key: Any) -> int:
    i = 0               #  1  |  O(1)

    while True:         # n/2 |  O(n)
        if a[i] == key: # n/2 |  O(n)
            return i    #  1  |  O(1)
        i += 1          # n/2 |  O(n)

    return -1           #  1  |  O(1)

• 전체 복잡도는 차원이 가장 높은 복잡도를 선택함
• 선형 검색 알고리즘의 복잡도는 O(n)

 

📚 이진 검색의 복잡도

def binary_search(a: Sequence, key: Any) -> int:
    pl = 0                  #  1  |  O(1)
    pr = len(a) - 1         #  1  |  O(1)

    while True:
        pc = (pl + pr) // 2 # log n |  O(log n)
        if a[pc] == key:    # log n |  O(log n)
            return pc       #  1  |  O(1)
        elif a[pc] < key:   # log n |  O(log n)
            pl = pc + 1     # log n |  O(log n)
        else:               # log n |  O(log n)
            pr = pc - 1     # log n |  O(log n)
        if pl > pr:         # log n |  O(log n)
            break           #  1  |  O(1)

    return -1

• 이진 검색 알고리즘의 복잡도는 O(log n)

 

📌 해시법

📚 해시법 (hashing)

• 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있는 해시법
• 데이터를 저장할 위치 = 인덱스
• 연산값은 해시값(hash value)이 되어, 데이터에 접근할 때 기준이 됨
• 해시값을 인덱스로 하여 원소를 새로 지정한 배열이 해시 테이블(hash table)
• 키를 해시값으로 변환하는 과정을 해시함수(hashing function)
• 해시 테이블에서 만들어진 원소가 버킷(bucket)

 

📚 해시 충돌(collision)

• 저장할 버킷이 중복되는 현상
• 해결 방법
  • 체인법 : 해시값이 같은 원소를 연결 리스트로 관리합니다
  • 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복합니다.

 

📚 체인법

📃 체인법

• = 오픈 해시법
• 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결
• 배열의 각 버킷에 저장하는 것은 인덱스를 해시값으로 하는 연결리스트의 앞쪽 노드를 참조

 

📃 Node 클래스

from __future__ import annotations
from typing import Any, Type
import hashlib

class Node:
    """해시를 구성하는 노드"""

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

• key: 키 / value: 값 / next: 뒤쪽 노드 참고
• next : 자기 참조형 클래스

 

📃 ChainedHash 클래스

class ChainedHash:
    """체인법으로 해시 클래스 구현"""
    
    def __init__(self, capacity: int) -> None:
        """초기화"""
        self.capacity = capacity
        self.table = [None] * self.capacity
    
    def 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)

• capacity: 해시테이블의 크기(배열 table의 원소 수)
• table: 해시 테이블을 저장하는 list형 배열을 나타냅니다.
• __init__( )
  • 빈 해시 테이블을 생성
  • 매개변수 capacity에 전달받는 것은 해시 테이블의 크기
  • 원소수가 capacity인 list형의 배열 table을 생성하고 원소를 None으로 설정
• hash_value( )
  • 인수 key에 대응하는 해시 값을 구함

 

📃 해시, 해시함수

• 충돌이 전혀 발생하지 않는다면 해시 함수로 인덱스를 찾는것만으로도 검색, 추가, 삭제가 가능
• 시간 복잡도는 O(1)
• 시간과 공간의 트레이드-오프 관계
• 충돌을 버리기 위해 해시 함수가 해시 테이블 크기보다 작거나 같은 정수를 고르게 생성

 

📃 hash_value( ) 함수

• key가 int 형인 경우와 아닌 경우로 나눔
• key가 int형인 경우
  • key를 capacity로 나눈 나머지 값을 해시값으로 설정
• key가 int형이 아닌 경우
  • key가 정수가 아닌 경우(문자열, 리스트, 클래스형 등) 값으로 나눌 수 없음
  • 표준 라이브러리로 형변환 후 해시값 생성

1. sha256알고리즘 : hashlib 모듈에서 제공하는 sha256, 주어진 바이트 문자열의 해시값을 구하는 해시 알고리즘의 생성자(constructor)
2. encode() 함수 : hashlib.sha256에서 바이트 문자열의 인수를 전달해야함, key를 str형 문자열로 변환한 후 문자열을 encode( ) 함수에 전달하여 바이트 문자열을 생성
3. hexdigest() 함수 : sha256 알고리즘에서 해시값을 16진수 문자열로 꺼냄
4. int() 함수 : hexdigiest() 함수로 꺼낸 문자열을 16진수 문자열로 하는 int 반환

 

📃 search( ) 함수

def search(self, key: Any) -> Any:
        """키가 key인 원소를 검색하여 값을 반환"""
        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

1. 해시 함수를 사용하여 키를 해시값으로 반환
2. 해시값을 인덱스로 하는 버킷에 주목
3. 버킷이 참조하는 연결리스트를 앞부터 스캔

 

📃 add( ) 함수

def add(self, key: Any, value: Any) -> bool:
        """키가 key이고 값이 value인 원소를 추가"""
        hash = self.hash_value(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

1. 해시 함수를 사용하여 키를 해시값으로 반환
2. 해시값을 인덱스로 하는 버킷에 주목
3. 버킷이 참조하는 연결리스트를 앞부터 스캔
4. 키와 같은 값이 발견되면 이미 있는 값이므로 등록 실패, 없다면 맨 앞에 노드를 추가

 

📃 remove( )

def remove(self, key: Any):
        """키가 key인 원소를 삭제"""
        hash = self.hash_value(key)
        p = self.table[hash]
        pp = None
        
        while p is not None:
            if p.key == 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

1. 해시 함수를 사용하여 키를 해시값으로 반환
2. 해시값을 인덱스로 하는 버킷에 주목
3. 버킷이 참조하는 연결리스트를 앞부터 선형 검색
4. 키와 같은 값이 발견되면 그 노트를 삭제

 

📃 dump( )

def dump(self) -> None:
        """해시 테이블을 덤프"""
        for i in range(self.capacity):
            p = self.table[i]
            print(i, end='')
            while p is not None:
                print(f'  -> {p.key} ({p.value})', end='')
                p = p.next
            print()

• 해시 테이블읜 내용을 한꺼번에 통째로 출력
• 각 노드의 키와 값을 출력

 

📃 ChainedHash 클래스를 사용하는 프로그램

from enum import Enum
from chained_hash import ChainedHash

Menu = Enum('Menu', ['추가',  '삭제', '검색', '덤프', '종료'])

def select_menu() -> 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
• 해시 충돌이 발생했을 때 오픈 주소법은 재해시(rehashing)을 수행하여 빈 버킷을 찾음
• = 닫힌 해시법(closed hashing)
• 원소를 추가, 삭제, 검색

 

📃 원소 추가

• 빈 버킷이 나올 때까지 재해시를 반복하므로 선형 탐색법(linear probing)

 

📃 원소 삭제

• 버킷에 속성을 부여하여 데이터가 존재하지 않는다고 착각하지 않도록 함
  • 데이터가 저장되어 있음(숫자)
  • 비어있음(-)
  • 삭제 완료(◉)

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) -> None:
        """초기화"""
        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

    def search_node(self, key: Any) -> Any:
        """키가 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: Any) -> Any:
        p = self.search_node(key)
        if p is not None:   # 검색 성공
            return p.value
        else:               # 검색 실패
            return None
    
    def add(self, key: Any, value: Any) -> bool:
        """키가 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.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) -> int:
        """키가 key인 원소를 삭제"""
        p = self.search_node(key)   # 버킷을 주목
        if p is None:
            return False            # 이 키는 등록되지 않음
        p.set_status(Status.DELETED)
        return True
    
    def dump(self) -> None:
        """해시 테이블을 덤프"""
        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.DELETED:
                print('--삭제 완료--')