🔊 주의사항
책에 있는 실습과 내용을 똑같이 적으면 저작권 문제가 될 수도 있기 때문에 약간의 변형을 하여 작성하였습니다. (특히, 실습 코드)
🪄 맛보기
| 선형검색 | 이진검색 | 해시법 |
|---|---|---|
| 무작위로 늘어놓은 데이터 집합에서 검색 | 일정한규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색 | 추가 및 삭제가 일어나는 데이터 집합에서 아주 빠른 검색 ▶ 방법 : 체인법, 오픈 주소법 존재 |
📚 03-2 선형 검색
선형 검색(Linear search)
🔎 참고자료
DelftStack python의 선형 검색
geeksforgeeks Python Program for Linear Search
wikidocs 탐색/검색(search)
배열에서 가장 기본적인 알고리즘으로 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색한다.
즉, 처음부터 끝까지 순서대로 탐색을 하는 알고리즘이다.
선형 검색은 순차 검색(Sequential search)라고도 부른다.
📑 선형 검색의 종료 조건
1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 ▶ 검색 실패
2. 검색할 값과 같은 원소를 찾는 경우 ▶ 검색 성공
def linear_search(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i
return 'X'
test1_lst = [1,2,3,4,5]
test2_lst = ['가','나','다','라']
test3_lst = [3.14, 'luna', 50, 'Amy', 77.32, 2.717]
test4_lst = ['철수', '짱구', '맹구', '훈이', '유리']
print(f'정수 4의 인덱스는 {linear_search(test1_lst, 4)} 입니다.')
print(f'문자 "나"의 인덱스는 {linear_search(test2_lst, "나")} 입니다.')
print(f'실수 77.32의 인덱스는 {linear_search(test3_lst, 77.32)} 입니다.')
# test4_lst에 원소 "치타"가 존재하지 않기 때문에 return "X" 반환
print(f'"치타"의 인덱스는 {linear_search(test4_lst, "치타")} 입니다.')보초법(Sentinel method)
선형 검색에서 반복을 종료하는 판단 횟수를 줄이는 역할로 검사하는 비용(cost)을 줄여준다.
즉, 보초법을 사용하면 배열 맨 끝까지 도달하는 판단을 하지 않아도 된다.
📑 보초를 이용하여 선형검색을 하는 경우
1. 검색할 값을 배열의 마지막에 추가 → 검색 → 검색한 값과 같은 원소 발견 ▶ 검색 성공
2. 검색할 값을 배열의 마지막에 추가 → 검색 → 검색한 값과 같은 원소(보초) 발견 ▶ 검색 실패
import copy
def sentinel_m(lst, k):
a = copy.deepcopy(lst)
a.append(k)
i = 0
while True:
if a[i] == k:
break
i += 1
return -1 if i == len(lst) else i
test_lst = [1,5,2,7,9,10,23]
print(f'정수 9의 인덱스 : {sentinel_m(test_lst, 9)}')
print(f'정수 99의 인덱스 : {sentinel_m(test_lst, 99)}')🍬 return -1 if i == len(lst) else i
i == len(lst)값이 같으면 -1을 반환, 같지 않으면 i 인덱스 값을 반환한다.
- 반환 값 -1인 경우 : 배열의 처음부터 끝까지 검색했지만 검색 값을 찾지 못한 경우 ▶ 검색 실패
- 반환 값 i인 경우 : 배열을 검색하는 도중 검색 값을 찾은 경우 ▶ 검색 성공
if문을 풀어서 작성하면 다음과 같다.
if i == len(lst):
return -1
else:
return i📚 03-3 이진 검색
이진검색(Binary search)
🔎 참고자료
프로그래머스 이진 탐색하기
잔재미코딩 이진 탐색
이진 검색은 정렬된 배열을 효율적으로 검색할 수 있는 알고리즘으로 선형 검색보다 빠르게 검색할 수 있는 알고리즘이다.
특히, 이진 검색에서는 배열이 오름차순으로 정렬되어 있어야 한다.
# pr : 배열 오른쪽
# pl : 배열 왼쪽
# pc : 배열 중앙
def binary_search(lst, k):
pl = 0
pr = len(lst) - 1
while True:
pc = (pl + pr) // 2
if lst[pc] == k:
return pc
elif lst[pc] < k:
pl = pc + 1
else:
pr = pc - 1
if pl > pr:
break
return -1
# 오름차순
asc_lst = [1,4,7,9,10,20,43]
print(f'asc_lst 정수 10의 인덱스 : {binary_search(asc_lst, 10)}')
print(f'asc_lst 정수 100의 인덱스 : {binary_search(asc_lst, 100)}')복잡도(Complexity)
🔎 참고자료
잔재미코딩 알고리즘 복잡도 표현방법
잔재미코딩 알고리즘 복잡도 (시간복잡도)
Dev JaykO 파이썬: 자료형 별 연산자의 시간복잡도(Big-O) 정리
알고리즘 성능을 객관적으로 평가하는 기준으로 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다.
- 시간 복잡도(Time Complexity) : 알고리즘 실행 속도
- 공간 복잡도(Space Complexity) : 알고리즘이 사용하는 메모리(기억 공간) 사이즈
📚 03-4 해시법
해시법(Hashing)
🔎 참고자료
잔재미코딩 대표적인 자료구조: 해쉬테이블
ComDoc 해싱(hasing), 파이썬
wikidocs 해쉬 테이블
SoniaComp 파이썬 해시테이블
검색과 더불어 데이터 추가 및 삭제을 효율적으로 수행할 수 있다. 해시법을 사용하여 데이터를 저장할 위치 = 인덱스를 간단한 연산으로 구한다.
- 해시 함수(hash function) : 해시값으로 변환하는 과정
- 버킷(bucket) : 해시 테이블에서 만들어진 원소
🍬 장점
1. 데이터 저장 및 읽기 속도 빠름 ▶ 검색 속도 빠름
2. 중복 확인 쉬움
🍬 단점
1. 저장공간이 많이 필요함
2. 저장할 버킷이 충돌하는 경우 해결 방법 필요 ▶ 체인법과 오픈 주소법
해시 충돌(Hash Collision)
값을 추가할 때 값이 이미 존재하는 경우 충돌이 발생하게 된다. 즉, 저장할 버킷이 중복되는 현상을 말한다.
해시 충돌을 막기 위해서 두 가지 방법이 존재한다.
- 체인법 : 해시값이 같은 원소를 연결 리스트로 관리
- 오픈 주소법 : 빈 버킷을 찾을 때 까지 해시를 반복
체인법(Chaining)
해시값이 같은 데이터를 체인(chain)모양의 연결 리스트로 연결하는 방법이며 오픈 해시법(Open Hashing)이라고도 한다.
🪄 구현
- Node 클래스 생성
| key | value | next |
|---|---|---|
| 키 (임의의 자료형) | 값 (임의의 자료형) | 뒤쪽 노드를 참조 (Node형) |
- ChainedHash 해시 클래스 생성
| capacity | table |
|---|---|
| 해시 테이블의 크기(배열 table의 원소 수) | 해시 테이블을 저장하는 list형 배열 |
-
hash_value 해시 함수 생성
▶ key에 대응하는 해시값을 구함 -
키로 원소를 검색하는 search() 함수 생성
▶ key인 원소를 검색 -
원소를 추가하는 add() 함수 생성
▶ 키가 key이고 값이 value인 원소를 추가
-
원소를 삭제하는 search() 함수 생성
▶ 키가 key인 원소를 삭제 -
원소를 출력하는 dump() 함수 생성
▶ 해시 테이블의 내용을 모두 출력
오픈 주소법(Open Addressing)
🔎 참고자료
yoongrammer 개방 주소법
오픈 주소법은 충돌이 발생했을 때 재해시(Rehasing)를 수행하여 빈 버킷을 찾는 방법을 말하며 닫인 해시법(Close Hahashing)이라고도 한다.
빈 버킷이 나올 때까지 재해시를 반복하므로 선형 탐사범(Linear Probing)이라고도 한다.
