[Algorithm] 검색 알고리즘_1

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

검색과 키

---

• 국적이 한국인 사람을 찾습니다.
• 나이가 21세 이상 27세 미만인 사람을 찾습니다.
• 이름에 '민' 자가 들어간 사람을 찾습니다.

---

• 모두 어떠한 항목에 주목하고 있습니다.
• 이렇게 주목하는 항목을 키(key)라고 합니다.
• 대부분 키는 데이터의 일부입니다.
• 국적: 키값과 일치하도록 지정합니다.
• 나이: 키값의 구간을 지정합니다.
• 문자: 키값에 가깝도록 지정합니다.

---

검색의 종류

1. 배열 검색
2. 연결 리스트 검색
3. 이진 검색 트리 검색

 

검색의 종류

---

배열 검색

• 선형 검색: 무작위로 늘어놓은 데이터 집합에서 검색을 수행합니다.
• 이진 검색: 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행합니다.
• 해시법: 추가·삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수해합니다.
  - 체인법: 같은 해시값 데이터를 연결 리스트로 연결하는 방법입니다.
  - 오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법입니다.

 

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