[5.5-6] 03 검색 알고리즘

03-3 이진 검색 binary search

이진 검색

오름차순/내림차순으로 정렬된 배열. 

업데이트하는 식으로 정렬함. 

종료 조건 - 위치를 찾거나 / 없는 경우

#이진 검색 알고리즘

def binary(a, k):
  n = len(a)
  pl = 0
  while True:
    pc = (pl + n) // 2
    if a[pc] == k:
      return pc
    elif a[pc] < k:
      pl = pc + 1
    else:
      n = pc - 1
    if pl > n:
      break
  return -1

print(binary([1, 2], 1))

- 시작값, 끝값을 새로 설정하고 조정한다.

from typing import Any, Sequence

def bin_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:
      pr = pc - 1
    else: 
      pl = pc + 1
    if pl > pr:
      break
  return -1

print(bin_search([1, 2], 3))

입력 내용

원소 수를 입력하세요

오름차순으로 입력하세요

검색값은 여기(출력)에 있습니다. 

복습

def binary(a, k):
  st = 0
  fin = len(a) - 1
  mid = (st + fin) // 2

  while True:
    if a[mid] == k:
      return mid
    elif a[mid] > k:
      fin = mid - 1
    else:
      st = mid + 1
    if st > fin:
      break
  return -1

print(binary([1, 2], 1)) 

복잡도

time complexity (실행 시간) / space complexity (메모리, 파일 공간)

#선형 검색의 시간 복잡도

def search(a, k):
  tr = 0
  i = 0
  while True:
    if a[i] == k:
      tr += 1
      print(tr)
      return i
      break
    i += 1
    tr += 1
    if i == len(a):
      break
  print(tr)
  return -1
print(search([1, 2, 3, 4, 5], 6))

-> O(n)

* index()

- 리스트, 튜플에서의 검색 수행. obj.index(x, i, j) -> obj[i:j] 안에 x있으면, 인덱스 반환 / ValueError

이진 검색의 시간 복잡도

from typing import Any, Sequence

def bin_search(a:Sequence, key:Any)-> int:

  pl = 0
  pr = len(a) - 1
  tr = 0

  while True:
    pc = (pl + pr) // 2
    tr += 1
    if a[pc] == key:
      print(tr)
      return pc
    elif a[pc] > key:
      pr = pc - 1
    else: 
      pl = pc + 1
    if pl > pr:
      break
  print(tr)
  return -1


print(bin_search([1, 2], 2))

O(logn)

from typing import Any, Sequence

def bin_search(a:Sequence, key:Any)-> int:
  pl=0
  pr=len(a)-1

  print('   :', end='')
  for i in range(len(a)):
    print(f'{i:4}', end='')
  print()
  print('---+' + (4*len(a)+2)*'-')

  while True:
    pc = (pl+pr) // 2
    print('   :', end='')
    if pl != pc:
      print((pl*4+1)*' ' + '<-' + ((pc-pl)*4)*' '+'+', end='')
    else:
      print((pc*4+1)*' ' + '<+', end='')
    if pc != pr:
      print(((pr-pc)*4-2)*'-'+'->')
    else:
      print('->')
    print(f'{pc:3}:', end='')

    for i in range(len(a)):
      print(f'{a[i]:4}', end='')
    print('\n   :')

    if a[pc] == key:
      return pc
    elif a[pc] > key:
      pr = pc -1
    else:
      pl = 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(idx)
  

03-4 해시법 hashing

해시법

- 데이터를 저장할 위치 : 인덱스를 연산으로 구현하는 것 -> 검색/추가/삭제가 효율적임

해시 충돌

해시 충돌 대처법에 따라 체인법 / 오픈 주소법으로 나뉨. 

체인법 chaining

체인법 - 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법. open hashing

#체인법으로 해시 함수 구현하기

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

Node 클래스 만들기

key : Any

value : Any

next : Node

ChainedHash 해시 클래스 만들기

from typing import Any, Type
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)

__init__() 함수로 초기화하기

 

hash_value() 해시 함수 만들기

키로 원소를 검색하는 search() 함수 만들기

오픈 주소법