[4.28] 검색 알고리즘

03장 검색 알고리즘

- 데이터 집합에서 원하는 값을 가진 원소를 찾아내는 검색 알고리즘

03-1 검색 알고리즘이란?

검색과 키

- 검색 : 어떤 조건을 만족하는 데이터를 찾아내는 것

- 키 key :  데이터에서 주목하는 항목

검색의 종류

- 배열 검색 : 선형 검색, 이진 검색, 해시법(체인법, 오픈 주소법)

: 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색 수행

: 이진 검색 : 일정한 규칙으로 배열한 데이터 집합에서 빠른 검색 수행

: 해시법 : 추가, 삭제가 자주 일어나는 데이터 집합에서 빠른 검색 수행

- 연결 리스트 검색

- 이진 검색 트리 검색

03-2 선형 검색

선형 검색

linear search : 선형으로 늘어선 배열에서, 맨 앞에서부터 스캔하여 순서대로 검색하는 알고리즘

= sequential search

선형검색의 종료조건 - 검색 실패 / 검색 성공

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

def search():
  n = int(input('원소 개수 : '))
  x = []
  for i in range(n):
    k = int(input(f'x[{i}]값은 : '))
    x.append(k)
  q = int(input('찾는 값: '))
  i = 0
  while True:
    if x[i] == q:
      return i
    else:
      i += 1
  return -1

print(search())

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

def search():
  n = int(input('원소 개수 : '))
  x = []
  for i in range(n):
    k = int(input(f'x[{i}]값은 : '))
    x.append(k)
  q = int(input('찾는 값: '))
  for i in range(n):
    if x[i] == q:
      return i
  else:
    return -1

print(search())

예제 코드

- from typing import Any, Sequence

- def seq_search(a: Sequence, Key : Any) -> int:

#입력 : 원소 수, 각 원솟값, 검색할 값 출력 : 검색한 값의 위치

다양한 자료형인 시퀀스에서 검색

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

#End를 입력하면 종료한다. 
number = 0
x = []

while True:
  s = input(f'x[{number}]:')
  if s == 'End':
    break
  else:
    x.append(float(s))
    number += 1

ky = float(input('검색할 값은? '))
idx = seq_search(x, ky)

if idx == -1:
  print('없음')
else:
  print(idx)

보초법 

sentinel method - 비용을 반으로 줄이는 방법

검색하고자 하는 키값을 배열 맨 끝에 저장한다. 이게 sentinel 보초

-> 종료조건을 하나로 줄여준다. 

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

from typing import Any, Sequence

def seq_search(a:Sequence, key: Any) -> int:
  i = 0

  while True:
    if a[i] == key:
      return i
    i =+ 1
  
if __name__ == '__main__':
  num = int(input('원소 수는 : '))
  x = [None] * num

  for i in range(num):
    x[i] = int(input(f'{i}번째 원소: '))
  
  ky = int(input('검색할 값: '))
  x.append(ky)

  idx = seq_search(x, ky)

  if idx == len(x):
    print('없음')
  else:
    print(idx)

03-3 이진 검색

이진 검색

복잡도

03-4 해시법

정렬된 배열에서 원소 추가하기

해시법

해시 충돌

체인법

오픈 주소법