티스토리 뷰
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다.
* 순차 검색(Sequential Search)
- 일렬로 되어있는 자료를 처음부터 마지막까지 순서대로 검색하는 방법
- 선형 검색(Linear Search)라고도 함
- 가장 간단하고 직접적인 방법으로, 배열이나 연결 리스트로 구현된 순차 자료구조에서 원하는 항목을 찾는 방법
* 순차 검색 장/단점
[장점]
- 알고리즘이 단순하여 구현이 쉬움
[단점]
- 검색해야 하는 자료의 양에 따라 효율이 달라져서 자료가 아주 많은 경우 비효율적임
* 색인 순차 검색(Index Sequential Search)
- 인덱스 테이블(Index Table)은 배열에 정렬되어 있는 자료 중에서 일정한 간격으로 떨어져 있는 원소들을 가지고 있음
- 인덱스 테이블을 추가로 사용하여 탐색의 효율을 높인 검색 방법
* 이진 검색(Binary Search)
- 자료의 가운데에 있는 항목을 키값과 비교하여 키값이 더 크면 오른쪽 부분을 검색하고, 키값이 더 작으면 왼쪽 부분을 검색하는 방법
- 이분 검색 또는 분간 검색(Intertpolation Search)라고도 함
[탐색 성공]
[탐색 실패]
* 이진 검색 장/단점
[장점]
- 시간 복잡도가 O(logn)으로 다른 검색 방법에 비해 성능이 좋음
[단점]
- 삽입이나 삭제를 수행한 후에 항상 배열의 상태를 정렬된 상태로 유지해야 하는 작업이 추가로 필요함
* 이진 트리 검색(Binary Tree Search)
- 이진 탐색 트리를 사용하여 검색하는 방법
- 이진 탐색 트리는 중위 순회 방법으로 순회하면 오름차순으로 정렬된 자료를 구할 수 있음
*. 이진 트리 검색 장/단점
[장점]
- 이진 탐색 트리의 특성을 이용하여 쉽게 검색할 수 있음
[단점]
- 원소의 삽입이나 삭제 연산에서 항상 이진 탐색 트리를 재구성하여 유지해야 함
* 해싱(Hashing)
- 키값을 비교하여 찾는 검색 방법이 아닌 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식
- 해싱 함수(Hashing Function) : 키값을 원소의 위치로 변환하는 함수
- 해시 테이블(Hash Table) : 해싱 함수에 의해 계산된 주소의 위치에 항목을 저장한 표
- 해싱 검색 방법 : 키값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패
* 해싱 구조 용어
- 동거자 : 서로 다른 키값을 가지지만 해싱 함수에 의해서 같은 버킷에 저장된 키값들
- 충돌 : 서로 다른 키값에 대해 해싱 함수에 의해 주어진 버킷 주소가 같은 경우를 뜻함
(참고) 충돌이 발생한 경우에는 비어있는 슬롯에 동거자 관계로 키값을 저장하면 되지만, 비어있는 슬롯이 없는 경우에는 그 버킷을 지정받은 키값이 있어서 다시 충돌이 발생하면 오버플로우가 됨
- 키값 밀도 = 실제 사용중인 키값의 개수 / 사용 가능한 키값의 개수
- 적재 밀도 = 실제 사용중인 키값의 개수 / 해시 테이블에 저장 가능한 전체 키값의 개수
= 실제 사용중인 키값의 개수 / 버킷 개수 * 슬롯 개수
* 해싱 함수
- 키값의 위치를 계산하는 함수로, 해싱 검색에서 가장 중요함
- 좋은 해싱 함수의 조건
1) 해싱 함수는 계산이 쉬워야 한다.
2) 해싱 함수는 충돌이 적어야 한다.
3) 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.
* 해싱 함수의 종류
1) 중간 제곱 함수 : 키값을 제곱한 결과값에서 중간에 있는 적당한 비트를 주소로 사용하는 방법
2) 제산 함수 : 나머지 연산자 mod를 사용하는 방법으로서, 키값 k를 해시 테이블의 크기 M으로 나눈 나머지를 해시 주소로 사용함
h(k) = k mod M
3) 승산 함수 : 곱하기 연산을 사용하는 방법인데, 키값 k와 정해진 실수 a를 곱한 결과에서 소수점 이하 부분만을 테이블 크기 M과 곱해 그 정수 값을 주소로 사용함
4) 접지 함수 : 키의 비트 수가 해시 테이블 인덱스의 비트 수보다 큰 경우에 주로 사용하는 방법
5) 숫자 분석 함수 : 키값을 이루고 있는 각 자릿수의 분포를 분석하여 해시 주소로 사용하는 방법
6) 진법 변환 함수 : 키값이 10진수가 아닌 다른 진수일 때, 10진수로 변환하고 해시 테이블 주소로 필요한 자릿수만큼만 하위 자리의 수를 사용하는 방법
7) 비트 추출 함수 : 해시 테이블의 크기가 2^k일 때 키값을 이진 비트로 놓고 임의의 위치에 있는 비트들을 추출하여 주소로 사용하는 방법
* 오버플로우 처리 방법
1) 선형 개방 주소법
- 해싱 함수로 구한 버킷에 빈 슬롯이 없어서 오버플로우가 발생하면 그 다음 버킷에 빈 슬롯이 있는지 조사함
- 빈 슬롯이 있으면 키값을 저장하고, 빈 슬롯이 없으면 다시 그 다음 버킷을 조사함
- 위 과정을 되풀이하면서 해시 테이블 내에 비어있는 슬롯을 순차적으로 찾아서 사용하여 오버플로우 문제 처리
2) 체이닝
- 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키값을 저장할 수 있도록 하는 방법
- 버킷에 슬롯을 동적으로 삽입하고 삭제하기 위해서 연결 리스트를 사용함
- 각 버킷에 대한 헤드 노드를 1차원 배열로 만들고 각 버킷에 대한 헤드 노드는 슬롯을 연결 리스트로 가지고 있어서 슬롯의 삽입이나 삭제 연산을 쉽게 수행할 수 있음
'개인공부 > 자료구조|알고리즘' 카테고리의 다른 글
| [자료구조] 정렬(Sort) 개념 (0) | 2023.11.22 |
|---|---|
| [자료구조] 그래프(Graph) (0) | 2023.11.22 |
| [자료구조] 트리(Tree) (0) | 2023.11.20 |
| [자료구조] 큐(Queue) (0) | 2023.11.20 |
| [자료구조] 스택(Stack) (0) | 2023.11.20 |