TIL 날짜
2023.11.29
Contents
- 의미 및 요소
- 종류
- 문자열 검색 알고리
검색 알고리즘 의미 및 요소
의미: 검색 문제를 해결하기 위한 알고리즘
요소: 검색 단어, 페이지의 관련성 및 유용성, 출처의 전문성, 사용자의 위치 및 설정
검색 알고리즘의 종류
선형 검색 (순차탐색)
배열을 검색하는 방법 가운데 가장 기본적인 알고리즘
의미: 리스트나 배열과 같은 데이터 구조에서 원하는 값을 찾기 위한 검색 알고리즘
동작 방식: 처음 부터 시작하여 순차적으로 각 요소를 확인하여 진행종료 방식: 원하는 값 발견, 배열의 끝 도달시간 복잡도: Best O(1) Average O(n) Worst O(n)
예시
function linearSearch(arr, val){
// 반복문을 통해 배열의 끝까지 조사
for(var i = 0; i < arr.length; i++){
if(arr[i] === val) return i;
}
// 값이 없을 경우 -1을 반환
return -1;
}
linearSearch([34,51,1,2,3,45,56,687], 100) // -1
이진 검색 (이분검색)
정렬된 배열에 작업해야 효율적으로 검색이 가능한 알고리즘
의미:
특정 자료구조(정렬된 배열)에 작업하여 효율적으로 작업하여 원하는 값을 추출하는 알고리즘동작 방식: 시작 요소, 끝 요소, 중앙 요소를 기준으로 중앙요소와 값이 같아질때까지 반복종료 조건: 중앙 요소와 원하는 값이 같을 경우, 검색 범위가 더이상 없는 경우시간 복잡도: O(log N)
예시
function middleSearch(arr, elem) {
var start = 0;
var end = arr.length - 1;
var middle = Math.floor((start + end) / 2);
while(arr[middle] !== elem && start <= end) {
if(elem < arr[middle]) end = middle - 1;
else start = middle + 1;
middle = Math.floor((start + end) / 2);
}
return arr[middle] === elem ? middle : -1;
}
middleSearch([2,5,6,9,13,15,28,30], 100) // -1
나이브 문자열 검색
의미: 기본적이고 흔한 선형 방식 알고리즘
동작 방식: 처음 부터 시작하여 순차적으로 각 요소를 확인하여 진행
종료 방식: 원하는 값 발견, 배열의 끝 도달
시간 복잡도: O(n*m) -> m:패턴의 길이, n:텍스트의 길이
예시
function naiveSearch(long, short){
let count = 0; //초기값
for(let i = 0; i < long.length; i++){
for(let j = 0; j < short.length; j++){
if(short[j] !== long[i+j]){
break;
}
if(j === short.length - 1){
count++;
}
}
}
return count;
}
naiveSearch("lorie loled", "lol"); // 1
참고
이미지 파일