검색
JS에서는 배열에 담긴 element를 조사하기 위한 다양한 방법이 있다. 그 중 하나가 indexOf를 이용한 검색 (없으면 -1 반환)
- 내장함수 원리에 대한 공부
- 어떻게 활용할 수 있을지 공부
목표
- 탐색 알고리즘(Searching Algorithm)은 무엇인가
- 배열에 대한 선형 탐색(linear search) 수행
- 정렬된 배열에 대한 이진 탐색(binary search) 수행
- naive한 String 탐색 알고리즘 구현
- KMP String 탐색 알고리즘이라 불리는 것 구현
선형 탐색(Linear Search)
- indexOf
Array - arr.indexOf(searchElement[, fromIndex])
배열에서 지정된 요소를 찾을 수 있는 첫 번째 인덱스를 반환하고 존재하지 않으면 -1을 반환
String - str.indexOf(searchValue[, fromIndex])
메서드는 호출한 String 객체에서 주어진 값과 일치하는 첫 번째 인덱스를 반환. 일치하는 값이 없으면 -1을 반환
- includes
Array - arr.includes(valueToFind[, fromIndex])
배열이 특정 요소를 포함하고 있는지 판별 true || false
String - str.includes(searchString[, position])
하나의 문자열이 다른 문자열에 포함되어 있는지를 판별하고, 결과를 true 또는 false 로 반환
- find - arr.find(callback[, thisArg])
주어진 판별 함수를 만족하는 첫 번째 요소의 값을 반환. 그런 요소가 없다면 undefined를 반환
- findIndex - arr.findIndex(callback(element[, index[, array]])[, thisArg])
주어진 판별 함수를 만족하는 배열의 첫 번째 요소에 대한 인덱스를, 만족하는 요소가 없으면 -1을 반환
이 4개는 실제로 선형탐색을 사용한다. 모든 요소를 한 번에 하나씩 확인
확실한 것은 일정한 간격으로 한 번에 한 요소씩 확인하면서 모든 것을 거쳐간다는 것
시간 복잡도 - O(n)
- Best : O(1)
- Average : O(n)
- Worst : O(n)
이진 탐색(Binary Search)
- 선형 탐색보다 훨씬 빠르다. 하지만 정렬된 배열에서만 사용 가능하다.
- 핵심은 분할 정복(divide and conquer)
- 정렬 된 배열에서 탐색하는 창문을 바꾸는 과정
- 탐색하고자 하는 값을 배열의 가운데 index 값과 비교 → 절반 삭제 → 반복
< 의사 코드(Pseudo Code) 작성 >
- 정렬된 배열
- 2가지 변수 - 1. left pointer, 2. right pointer
- loop 1. 조건에 부합한 요소를 찾았는가, 만족하지 못했다면 loop 돌기 2. left와 right가 만나기 전까지만 loop 돌기
- left와 right index의 절반 index 고르기
- 해당 index 값이 같다면 조건 만족, 작다면 left 올리기, 크다면 right 내리기.
- 값을 찾지 못했다면 -1 반환
정렬되지 않은 배열에서 탐색은 선형 탐색이 최선
시간 복잡도 - O(log n)
- Best : O(1)
- Average : O(log n)
- Worst : O(log n)
stringSearchNaive
function stringSearchNaive(long, short) {
var count = 0; // 일치하는 개수 담을 count 변수
for (var i = 0; i < long.length; i++) { // 긴 문자열을 전부 다 돌변서
for (var j = 0; j < short.length; j++) { // 짧은 문자열에 대하여
if (short[j] !== long[i + j]) break; // 비교 문자열끼리 일치하지 않으면 for문 탈출
if (j === short.length - 1) count++; // short를 다 돌면 비교 문자열이 일치하므로 count 1 증가
}
}
return count;
}
stringSearchNaive("lorie loled", "lol");시간복잡도 O(n*m)
KMP 알고리즘
https://www.youtube.com/watch?v=yWWbLrV4PZ8
https://gusdnd852.tistory.com/172 → 자세하게 잘 쓰여있는 블로그
https://junstar92.tistory.com/112 → 위의 블로그 보고 보면 이해 확 될만한 글
https://kbw1101.tistory.com/54 → 실패 함수의 목적에 대해 적어줌
Naive 알고리즘은 긴 문자열(long)의 모든 문자에 대해서 짧은 문자열(short)을 전부 비교해주기 때문에 최악의 경우 O(n*m)의 시간 복잡도를 갖는다.
- 비교가 불필요한 부분은 빠르게 점프
- 접두사(prefix)와 접미사(suffix) 활용 → 매칭이 실패할 경우 얼마나 점프할 수 있을지에 대한 정보를 구할 수 있는 실패시 작동 할 함수 구현
- 시간 복잡도 O(n+m)
구현 원리
- long에 대해서 short를 index 0부터 비교한다.
- character가 일치하면 두 문자열(long, short)의 각각의 포인터도 증가
- 불일치 이벤트 발생시(한칸씩 오른쪽으로 이동하는 브루트 포스 등의 완전 탐색과는 달리) short string이 불일치가 발생한 index로 점프 → 이거 중요
- 이게 핵심 대부분의 설명들이 왜 failure funtion이 필요한지에 대해 설명해주지 않는데, jump할 short string의 index를 결정지어주는 것이 lps table이다.
- lps 덕분에 suffix, prefix 일치 개수를 알 수 있으므로 불일치 지점으로 이동된 short index가 jump해온다.
- 5번 조정까지 완료 되고서 다시 탐색
- 결과적으로 브루트포스보다 빠르게 탐색 가능
→ 코드, 예시를 통해 이해 가능
LPS 테이블(Logest Prefix & Suffix) ← 실패 함수(failure function)로 만듦
- LPS 테이블은 짧은 문자열(short)에 대해 만드는 것
'문자 매칭에 실패했을 때, 얼만큼 건너뛰어야 하는가?'를 알기 위해 사용
short[0:i] = abcdabd
| i | short[0:i] | failure(i) |
|---|---|---|
| 0 | a | 0 |
| 1 | ab | 0 |
| 2 | abc | 0 |
| 3 | abcd | 0 |
| 4 | abcda | 1 |
| 5 | abcdab | 2 |
| 6 | abcdabd | 0 |
short[0:i] = abcaabcabc
| i | short[0:i] | failure(i) |
|---|---|---|
| 0 | a | 0 |
| 1 | ab | 0 |
| 2 | abc | 0 |
| 3 | abca | 1 |
| 4 | abcaa | 1 |
| 5 | abcaab | 2 |
| 6 | abcaabc | 3 |
| 7 | abcaabca | 4 |
| 8 | abcaabcab | 2 |
| 9 | abcaabcabc | 3 |
short[0:i] = abcaabcaa
| i | short[0:i] | failure(i) |
|---|---|---|
| 0 | a | 0 |
| 1 | ab | 0 |
| 2 | abc | 0 |
| 3 | abca | 1 |
| 4 | abcaa | 1 |
| 5 | abcaab | 2 |
| 6 | abcaabc | 3 |
| 7 | abcaabca | 4 |
| 8 | abcaabcaa | 5 |
빨간색은 겹쳐서 비교되는 부분(중요하지 않은 부분 이런 경우의 수도 생각할 수 있도로 환기용)
prefix와 suffix가 일치하는 개수를 나타내는 테이블이다. short string 순회를 돌 때, index가 증가함에 따라 index까지의 substring의 suffix가 prefix와 몇개 일치하는지 따진다.
이를 이용해서 kmp 알고리즘에서 생각해보자
- short string의 i + 1에서 불일치가 발생했을 때, lsp 테이블 특정 index의 i까지의 string에서 파란색에 해당하는 suffix 만큼은 long string과 일치한다.(여기를 이해하는 것이 중요)
- 이는 곧 prefix와 일치하는 것이다.
- 따라서 추가적으로 해당 범위를 또 비교할 필요 없이 점프하면서 놓치지 않고 비교할 수 있다.
실패 함수(failure function)
이제부터는 일반적인 KMP 알고리즘 설명과 동일하게 가면 된다.
구현 원리 (Pseudo)
우선 table[0] = 0이다. 당연히
abacaaba 를 예시로 이해해보기
1. 초기 세팅 i = 1, j = 0
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o | |||||||
| table | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2. i 증가
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o | |||||||
| table | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3. 일치할 때는 count에 해당하는 j 증가시키면서 table[i]에다가 할당
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o | |||||||
| table | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
4. i 증가
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o |
5. 일치하지 않으면서 j가 0보다 클 때는 j에 table[j-1]에 저장된 count값(0)을 준다
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o |
6. i 증가
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o |
7. 일치할 때는 count에 해당하는 j 증가시키면서 table[i]에다가 할당
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o | |||||||
| table | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
8. i 증가
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o |
9. 일치하지 않으면서 j가 0보다 클 때는 j에 table[j-1]에 저장된 count값(0)을 준다
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o |
10. 일치할 때는 count에 해당하는 j 증가시키면서 table[i]에다가 할당
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o | |||||||
| table | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
11. i 증가
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o |
12. 일치할 때는 count에 해당하는 j 증가시키면서 table[i]에다가 할당
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o | |||||||
| table | 0 | 0 | 1 | 0 | 1 | 1 | 2 | 0 |
13. i 증가
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o |
14. 일치할 때는 count에 해당하는 j 증가시키면서 table[i]에다가 할당
| 문자열 | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|
| i 위치 | o | |||||||
| j 위치 | o | |||||||
| table | 0 | 0 | 1 | 0 | 1 | 1 | 2 | 3 |
15. i 증가 → for문 종료
구현한 코드
function lpsTable(str) {
const len = str.length;
let returnTable = new Array(len).fill(0);
for (let i = 1, j = 0; i < len; i++) {
while (j > 0 && str[i] !== str[j]) j = returnTable[j - 1];
if (str[i] === str[j]) returnTable[i] = ++j;
}
return returnTable;
}
function kmp(long, short) {
let table = lpsTable(short),
lenLong = long.length,
lenShort = short.length;
// console.log(table);
let j = 0, // short string의 pointer
count = 0,
result = [];
for (let i = 0; i < lenLong; i++) {
while (j > 0 && long[i] != short[j]) { // j가 0보다 크고(j=0이면 어차피 short jump 거리는 0) 문자열 비교가 일치하지 않을 때
j = table[j - 1]; // 불일치 전까지의 suffix에서 prefix랑 일치한 개수만큼 short에서 jump 가능 -> 이게 jump 후 땡기는 역할을 대신한다.
}
// console.log(`long : ${long[i]}, ${i} | short: ${short[j]}, ${j}`);
if (long[i] === short[j]) { // 비교 문자열끼리 일치할 때는
if (j === lenShort - 1) { // j 포인터가 short를 벗어나면 == 즉, 모두 일치할 경우
result.push(i - lenShort + 2); // 시작 index(i+1/*i는 0부터니까 1 더하고*/ - lenShort + 1/* 빼주면 시작 전 index 값이 나온다*/)
count++; // count 증가
j = table[j]; // 거기에서도 suffix랑 일치하는 prefix만큼 short string에서 jump 가능
} else {
j++; // j를 증가시키고 for문에서 i++하고 자연스레 비교된다.
}
}
}
console.log(count);
console.log(result.join(" "));
}
막상 적고 보니 설명이 많이 부족하다... 실시간으로 설명하면서는 이해시킬 수 있을 것 같았는데..ㅋㅋㅋ 확실히 어려운 알고리즘이라 설명이 어렵다.
문제
'CS > 알고리즘|자료구조' 카테고리의 다른 글
| 스터디 발표 준비 - 단일연결리스트(Singly Linked List) (0) | 2022.03.29 |
|---|---|
| [알고리즘] Sliding Window Pattern 심화 (0) | 2022.01.16 |
| [알고리즘] 문제해결패턴 (0) | 2022.01.15 |
| [자료구조] 시간복잡도 문제 풀기 (0) | 2022.01.02 |
| [Python|알고리즘] Sequential Search (0) | 2021.10.16 |
댓글