Searching Algorithms
Searching Algorithms
A presentation created with Slides.
cs.slides.com
1. 검색 소개
2. 선형 검색 소개
3. 선형 검색 솔루션
4. 선형 검색 빅오 (Big O)
5. 이진 검색 소개
6. 이진 검색 의사코드
7. 이진 검색 솔루션
8. 이진 검색 빅오 (Big O)
9. 나이브 문자열 검색
10. 나이브 문자열 검색 구현
0. 검색 소개
목표
1. 검색 알고리즘이 무엇인지 파악
2. 배열에서 선형검색 구현
3. 정렬된 배열에서 이진탐색 구현
4. 나이브(naive) 문자열 검색 알고리즘 구현
5. KMP 문자열 검색 알고리즘 구현
1. 선형 검색 소개
아래 메서드가 선형 탐색을 이용한다.
indexOf
includes
find
findIndex
2. 선형 검색 솔루션
// Linear Search Exercise
// Write a function called linearSearch which accepts an array and a value,
// and returns the index at which the value exists.
// If the value does not exist in the array, return -1
// Don't use indexOf to implement this function!
// Example:
linearSearch([10, 15, 20, 25, 30], 15) // 1
linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4) // 5
linearSearch([100], 100) // 0
linearSearch([1,2,3,4,5], 6) // -1
linearSearch([9,8,7,6,5,4,3,2,1,0], 10) //-1
linearSearch([100], 200) // -1
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}3. 선형 검색 빅오 (Big O)
선형 탐색의 BIG O
O(1) - Best
O(n) - Average
O(n) - Worst
4. 이진 검색 소개
1. 이진 탐색은 빠른 탐색이다.
2. 한번에 한 요소를 제거하는 것보다, 한번에 요소 절반을 제거할 수 있다.
3. 이진 탐색은 오직 정렬된 배열에서만 사용가능하다.
5. 이진 검색 의사코드
이진 탐색 의사코드
1. 함수의 인자로 정렬된 배열과 검색할 요소를 넣는다.
2. 배열의 제일 처음 자리에 왼쪽 포인터를 만든다. 배열의 마지막 자리에 오른쪽 포인터를 만든다.
3. 왼쪽포인터가 오른쪽 포인터 보다 작을 때는 반복문을 돌린다.
3-1. 중간 포인터를 만든다.
3-2. 만약에 검색할 요소를 찾았다면 인덱스를 반환한다.
3-3. 만약 검색할 요소가 중간 포인터 보다 작다면, 왼쪽요소를 중간요소 바로 뒤로 옮긴다.
3-4. 만약 검색할 요소가 중간 포인터 보다 크다면, 오른쪽요소를 중간요소 바로 앞으로 옮긴다.
4. 만약에 검색할 요소를 발견하지 못하면 -1을 반환한다.
6. 이진 검색 솔루션
This algorithm should be more efficient than linearSearch
- you can read how to implement it here
// Write a function called binarySearch which accepts a sorted array and a value
// and returns the index at which the value exists. Otherwise, return -1.
binarySearch([5,6,10,13,14,18,30,34,35,37,40,44,64,79,84,86,95,96,97,99], 95) // 16
function binarySearch(arr, val){
let left = 0;
let right = arr.length-1;
let mid;
while (left <= right) {
mid = parseInt((right + left)/2);
if (arr[mid] === val) return mid;
if (val > arr[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}실행 과정
Answer
// Original Solution
function binarySearch(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);
}
if(arr[middle] === elem){ // 여기
return middle; // 3줄
} // 리팩토링 하면
return -1; // return arr[middle] === elem ? middle : -1;
}
binarySearch([2,5,6,9,13,15,28,30], 103)7. 이진 검색 빅오 (Big O)
O(log n) - Worst and Average Case
O(1) - Best Case
8. 나이브(naive) 문자열 검색
긴 문자열에서 부분문자열의 개수를 셀 때를 가정해보자.
간단한 접근법은 문자 쌍을 개별적으로 확인하는 것이다.
의사코드
1. 긴 문자열을 반복문으로 돌린다.
2. 짧은 문자열을 반복문으로 돌린다.
3. 문자가 일치하지 않으면 내부 루프에서 벗어난다.
4. 문자가 일치하면 계속 진행한다.
5. 내부 루프를 완료하고 일치하는 항목을 찾으면 count를 1 늘린다.
6. count를 반환한다.
9. 나이브 문자열 검색 구현 🎁
function naiveSearch(long, short){
var count = 0;
for(var i = 0; i < long.length; i++){
for(var 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")실행순서
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l 🎉count++
-----------------------------
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l
-----------------------------
l o r i e l o l e d
l o l 🙅