검색 알고리즘 종류
선형 검색 - Linear Search
- 순차 탐색(Sequential Search)이라고도 부름
- 배열을 검색하는 방법 가운데 가장 기본적인 알고리즘
- 무작위로 늘어놓은 데이터 모임에서 검색
- 정렬되지 않은 리스트에서 데이터를 찾을 때 사용
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
- 알고리즘은 무조건 종료해야기에
- 선형 검색의 경우 키 값을 발견하거나, 배열의 끝에 도달했을 경우 종료
- 키 값에 해당하는 요소 값이 두개 이상인 경우 맨 처음에 위치한 요소 반환
- 시간 복잡도 : O(N)
- 판단하는 횟수 평균 N/2회
- N : 데이터 갯수
- 보초법 - sentinel method
- 종료 조건 검사 비용을 줄이기 위해 사용(비용 50% 감소)
- 키 값을 배열의 마지막 요소로 추가해 배열의 끝을 지나간 경우를 없애 비용 줄임
- 마지막에 원래 데이터인지 보초인지만 판단
이진(=이분) 검색(binarySearch)
- 일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색
- 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다는 것
- 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
- 범위 (시작 요소와 끝 요소, 중앙 요소) 세 가지를 기준으로 중앙 요소와 같아질 때까지 반복해서 갱신하며 키 값을 찾아감
- 범위가 계속해서 줄어들다 범위가 없기 직전에 선택한 중앙 요소 +-1을 이용해 시작하는 값 or 마지막에 위치한 값 설정해 키 값을 찾음
- 종료 조건
- 중앙 요소로 선정된 요소가 키 값과 같은 경우
- 검색 범위가 더 이상 없는 경우
- 검색에 필요한 비교 횟수의 평균값은 log2N(검색에 실패할 경우 log2(N+1), 성공할 경우 log2(N-1))
- 시간 복잡도 : O(log2N)
- 절반식 줄어든다는 점에서 퀵 정렬과 공통점
- 구현 방법
- 이진 탐색 트리 관련 : https://velog.io/@sung-ik-je/Tree-%ED%8A%B8%EB%A6%AC
자연 정렬
- 이진 검색 종류 중에 하나
- 문자열 정렬과는 다르게 사람이 봤을 때 자연스럽게 정렬이 되어 있는 것
- 자연 정렬이 되어 있지 않은 경우에는 제네릭 메서드 사용하면 된다
문자열 정렬
- 동일한 위치에 있는 문자의 대소 비교를 통해 정렬
해시법
- 추가 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행
체인법 - 같은 해시 값의 데이터를 선형 리스트로 연결
오픈 주소법 - 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법
완전 탐색(Brute Force)
- 가능한 모든 경우의 수를 다 구해서 값을 찾는 것
- 컴퓨터의 빠른 성능을 활용
- 효율성 측면에서는 최악의 방법
- 가장 확실하지만 그만큼 시간 오래걸림
- 방법
- 일반적으로 DFS, BFS 이용해 문제 해결
- 반복문, 재귀문
DFS
- Depth First Search, 깊이 우선 탐색
- 하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정
- tree에서 leaf node 도달이 우선, 최대한 멀리 있는 노드 우선 탐색
- stack 자료구조를 사용하며 노드가 방문되어 있지 않은 경우 한개씩 삽입
- 소요시간
BFS
- Breath First Search, 너비 우선 탐색
- 하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정
- tree 구조에서 leaf node가 우선이 아닌 계층이 우선, 가까운 노드 탐색 우선
- DFS와 달리 QUEUE를 사용하며 방문 안되어 있는 노드들 한 턴에 모두 삽입
- 일반적인 경우 실제 수행시간 DFS보다 좋은 편
참고
- 알고리즘 선택에 있어 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러 가지인 경우에는 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택해야 한다
- ex) 찾는 것과 찾아서 수정하는 것은 목적도 비용도 다르다.