[Doit! Python] 검색 알고리즘

교재: Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬편

검색 알고리즘

검색 알고리즘이란?

검색과 키

대부분의 키는 데이터의 일부

검색의 종류

1. 배열 검색
   • 선형 검색
     • 무작위 데이터 집합에서 검색 수행
   • 이진 검색
     • 일정 규칙을 늘어놓은 데이터 집합에서 빠름
   • 해시법
     • 추가/삭제가 자주 일어나는 데이터 집합에서 빠름
     • 체인법 - 같은 해시값 데이터를 연결 리스트로 연결하는 방법
     • 오픈 주소법 - 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
2. 연결 리스트 검색(8장)
3. 이진 검색 트리 검색(7장)

따라서, 용도/목적/실행 속도/자료구조 등 여러 사항을 고려해서 알고리즘을 선택해야한다.

선형 검색

원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘

• 배열에 원하는 값이 존재할 때 조건을 판단하는 횟수 = 배열 원소의 개수/2 번 ?
• 배열에 원하는 값이 존재하지 않을 때 조건을 판단하는 횟수 = n+1 번 or n 번

# while문으로 작성한 선형 검색 알고리즘
i = 0
while True:
    # 검색 실패
	  if i == len(a):
        return -1
    # 검색 성공(찾은 원소의 인덱스는 i, 맨 처음 발견한 원소의 index만 반환)
    if a[i] == key:
        return i
    i += 1

보초법(Sentinel method)

• 선형 검색의 단점
  • 반복할 때마다 2가지 종료 조건을 매번 체크합니다. ⇒ 비용⬆️

검색할 값을 배열의 맨 끝에 추가해서 보초로 사용하는 방법입니다. 선형 검색에서 매번 2가지 종료 조건을 체크하는데 사용하는 비용을 반으로 줄여줍니다.

• if i == len(a) ⇒ 수행할 필요X
• if a[i] == key
• 질문. 왜 실습3-3에서는 보초법을 사용해서 판단 횟수를 줄인 후에 다시 len(seq)에 대한 판단문을 수행하는지, 해당 구문이 있으면 판단횟수가 안 줄어든거 아닌가..!
• 질문. copy.deepcopy로 복사를 하는 이유? 복사하지 않고 수행했을 때 차이가 있는지
  [Python]Shallow copy & Deep copy (velog.io)