자료구조와 함께 배우는 알고리즘 입문 : 파이썬편 - 03 검색 알고리즘

03 챕터 공부시간: 02:27:19
이 글은 자신의 개념 정리를 위하여 작성한 것 입니다.

내가 만든 목차

1. 검색
2. 보초법
3. 복잡도
4. 해시법
5. 해시충동일 경우

1. 검색
선형 검색: 배열의 원소를 맨 앞부터 순서대로 스캔하여 검색

이진 검색: 배열의 원소를 가운데부터 스캔하여 검색

선형 검색 사용 - 정렬되어 있지않을 때 사용
이진 검색 사용 - 정렬되어 있을 때 사용

2. 보초법
보초법 : 선형 검색을 사용할 때 검색의 수를 줄이기 위해 맨 뒤에 찾는 요소의 값을 추가하는 방법

3. 복잡도
시간복잡도: 실행하는데 필요한 시간을 평가함
공간복잡도: 메모리(기억 공간)와 파일골 공간이 얼마나 필요한지를 평가함

4. 해시법
해시법 : '데이터를 저장할 위치 = 인텍스'를 간단한 연산으로 구하는 것

5. 해시충동일 경우

(1)체인법(오픈 해시법) : 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법
Node 클래스 만들기
ChainedHash 해시 클래스 만들기
인수key에 대응하는해시값을 구하는 hash_value() 해시 함수
키로 원소를 검색하는 search()함수
원소를 추가하는 add()함수
원소를 삭제하는 remove()함수
원소를 통째로 출력하는 dump()함수

(2)오픈 주소법(닫인 해시법) : 충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법
원소 추가하기
원소 삭제하기
원소 검색하기

이해는 되었지만 함수들을 직접 구현할 수 없을 것 같다.
앞으로 알고리즘 문제 풀면서 계속 익숙해져야 한다.