728x90
교재: Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬편
검색 알고리즘
검색 알고리즘이란?
검색과 키
대부분의 키는 데이터의 일부
검색의 종류
- 배열 검색
- 선형 검색
- 무작위 데이터 집합에서 검색 수행
- 이진 검색
- 일정 규칙을 늘어놓은 데이터 집합에서 빠름
- 해시법
- 추가/삭제가 자주 일어나는 데이터 집합에서 빠름
- 체인법 - 같은 해시값 데이터를 연결 리스트로 연결하는 방법
- 오픈 주소법 - 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
- 선형 검색
- 연결 리스트 검색(8장)
- 이진 검색 트리 검색(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)
728x90