06 검색 알고리즘

6.1 선형 검색(선형 탐색)
오늘 공부한 내용은 검색 알고리즘에 대해서 공부했다. 검색 알고리즘이란 예를 들어 회원가입시 아이디가 중복되는 경우 중복된 아이디가 있는지 없는지 확인을 해야하는 경우 등 이러한 문제를 해결하기 위한 일련의 과정이 바로 검색 알고리즘이다.

우선 자바스크립트는 다양한 검색 관련 메서드들을 제공하고 있다.
1. indexOf : 메서드를 통해 배열내에 해당 요소가 있다면 해당 요소의 인덱스 번호를 반환해주고, 없다면 -1을 반환한다.
2. includes : 배열 내에 특정 요소가 포함되어 있는지 확인하여 불리언값을 반환한다.
3. find : 자신을 호출한 배열의 요소를 순회하면서 인수로 전달된 콜백 함수를 호출하여 반환값이 true인 첫 번째 요소를 반환한다.
4. findIndex : 자신을 호출한 배열의 요소를 순회하면서 인수로 전달된 콜백 함수를 호출하여 반환값이 true인 첫 번째 요소를 반환한다.

그렇다면 배열 검색을 할 때 가장 좋은 방법은 무엇일까? 사실 가장 간단한 방법은 모든 개별 항목을 순서대로 살펴보면서 우리가 원하는 값인지 확인하는게 가장 간단한 방법일 것이다. 그리고 이러한 검색 방법이 선형 검색이다. 선형 검색은 배열의 처음부터 끝까지 이동하면서 맨 끝에 도달할 때까지 각 항목이 찾고자하는 요소가 있는지 하나 하나 확인하는 것이다. 첫 부분에서 시작해서 끝부분으로 이동하면서 한 번에 하나의 항목을 확인할 수도 있고, 반대로 끝 부분에서 시작하여 첫 부분으로 이동할 수도 있다.

선형 검색 코드 작성을 위한 의사코드(강사님이 알려주신 의사코드임)
1. 함수에 전달해야 하는 인수는 배열과 특정 값을 전달해야 한다.
2. 배열 전체에 대한 루프를 만든다.
3. 현재 확인 중인 배열 요소가 우리가 입력하는 값과 동일한지 확인해야 한다.
4. 만약 확인하고자 하는 요소가 배열내에 있다면 값의 인덱스를 반환해야 한다.
5. 반대로 존재하지 않는다면 -1을 반환하게 한다.

//선형 검색
function elemSearch(arr,num){
    for(let i = 0 ; i < arr.length ; i++){
        if(arr[i] === num){
            return i;
        }
    }
    return -1
}

console.log(elemSearch([1,2,3,4,5],3));

참고로 자바스크립트가 기본 제공하는 배열 검색 메서드들은 선형 검색으로 지원한다.

6.2 이진 검색(binary search)(이분 탐색)
선형 검색은 위에서 설명했듯이 하나 하나 요소들을 비교한다. 이번에는 한 단계 업그레이드 된 정렬이 된 데이터를 가지는 배열에서 사용할 수 있는 선형 검색보다 빠른 이진 검색에 대해서 알아보자. 이진 검색은 선형 검색보다 크게 개선된 알고리즘이다. 하지만 주의해야 할 점은 반드시 배열이 정렬되어 있는 값들을 가지고 있어야 이진 검색을 할 수 있다. 처음에 공부했던 대표적인 패턴 중 하나인 divide and conquer 즉, 분할 그리고 정복 패턴이다.

이진 검색 코드 작성을 위한 의사코드(강사님이 알려주신 의사코드임)
1. 함수는 정렬된 배열과 찾고자 하는 값을 인수로 받는다.
2. 3개의 변수를 만든다. 포인터 역할을 할 변수 2개와 중간을 가리키게 될 변수 1개를 만든다.
3. 포인터 역할을 할 변수 중 하나는 계산을 시작하는 좌측을 나타내는 인덱스로 0일 할당하고, 배열의 우측 끝을 가리키는 우측 포인터를 만들며 우측 포인터 변수에는 배열의 길이에서 1을 뺀 값을 할당한다. 따라서 좌측 포인터는 0, 우측 포인터는 배열.length - 1을 할당한다. 그리고 두 포인터의 평균을 나타내는 중간을 가리키는 변수를 만들고, 좌측 포인터와 우측 포인터의 평균을 이용한다.(소수점 방지를 위해 Math.floor로 내림이나 Math.ceil로 올림을 해줘야 한다.)
4. 그리고 두 가지를 확인해야 한다. 첫 번째로 항목을 찾았는지 확인한다. 찾지 못했다면 연산을 계속한다. 두 번째로 좌측 포인터가 우측 포인터보다 앞에 있는 동안에만 연산이 계속되어야 한다.
5. 만약 중간값이 찾고자 하는 값보다 작다면 좌측 포인터를 중간값 +1로 바꿔주고, 중간값이 찾고자 하는 값보다 크다면 우측 포인터를 중간값 -1로 바꿔준다. 값을 찾을때까지 연산을 계속한다.
6. 연산이 다 끝난 후에도 값을 찾지 못한다면 -1을 반환한다.

function indexFinder(arr, ele){
    let left = 0;
    let right = arr.length - 1;
    let middle = Math.floor((left + right) / 2);

    while(arr[middle] !== ele && left <= right){
        if(arr[middle] < ele){
            left = middle + 1;
        }else{
            right = middle -1;
        }
        middle = Math.floor((left + right) / 2);
    }
    if(arr[middle] === ele){
        return middle;
    }
    return -1
}

console.log(indexFinder([1,2,3,4,5,6,7,8,9],3));

굉장히 헷갈릴 수 있지만, 핵심은 정렬된 배열을 가지고 양쪽 끝을 가리키는 포인터를 만들고 중간을 선택한 다음 필요없는 나머지 부분은 버리는 과정을 반복해서 원하는 요소를 찾는것이다. 위의 코드를 조금 더 간결하게 작성해 보면 다음과 같다.

function indexFinder(arr, ele){
    let left = 0;
    let right = arr.length - 1;
    let middle = Math.floor((left + right) / 2);

    while(arr[middle] !== ele && left <= right){
        if(arr[middle] < ele) left = middle + 1;
        else right = middle -1;
        middle = Math.floor((left + right) / 2);
    }
    return arr[middle] === ele ? middle : -1 //삼항 조건 연산자로 표현
}

console.log(indexFinder([1,2,3,4,5,6,7,8,9],3));

중요한 점은 이진 검색은 O(logN) 시간 복잡도를 갖는다. 배열의 길이가 2배로 길어 지더라도 처리 과정은 한 번씩만 늘어난다. 즉, 로그 이의 이의 n+1...이 되기 때문에 결국 처리 과정은 한 번씩만 늘어나게 된다. 그렇기 때문에 O(1) 시간 복잡도 보다는 아니지만, 굉장히 시간 복잡도를 기준으로 봤을때 효율적인 검색 방법이다.

6.3 일반적인 문자열 검색 방법
긴 문자열에서 문자 하나 하나를 검색하는것은 메서드나 반복문을 통해서 쉽게 찾아낼 수 있다. 그렇다면 긴 문자열에서 부분 문자열을 검색하는 것은 어떻게 해야할까? 가장 일반적인 방법에 대해서 알아보자. 가장 기본적이고 간단한 접근법 중 하나는 두 문자열을 나란히 놓고서 한 번에 하나의 문자씩 비교하는 것이다. 예를 들어보자.

'wowomgzomg'문자열에서 'omg'가 포함되어 있는지, 몇 번들어가 있는지 확인하고자 한다.
wowomgzomg
omg비교
 omg비교
   omg비교
    omg비교
     omg비교
      omg비교
       omg비교
        omg비교
         omg비교
           이렇게 하나 하나 한 글자씩 옮겨가면서 일치하는게 있나 비교! 하는게
           가장 기본적인 방법임

긴 문자열에서 부분 문자열을 검색하기 위한 방법을 알려주는 의사코드(강사님이 알려주신 의사코드임)
1. 긴 문자열과 찾고자 하는 부분 문자열을 인수로 받는 함수를 만든다.
2. 긴 문자열을 반복하는 루프를 만든다.
3. 짧은 문자열을 반복하는 루프를 중첩루프로 만든다.
4. 반복되는 문자끼리 비교를 시작한다.
5. 만약 문자끼리의 비교가 일치하지 않는다면 짧은 문자 반복문의 루프에서 벗어난다.(break키워드)
6. 그리고 긴 문자열의 문자와 반복되는 짧은 문자를 하나씩 비교하여 일치하면 다음 문자로 넘어간다.
7. 일치하는 문자열을 찾으면 내부 루프를 완료하고 카운트를 증가시키고, 카운트를 반환한다.
8. 카운트를 0에서 시작하면 별도의 오류 처리는 필요하지 않는다.

function strFinder(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; //여기서 i는 비교를 시작할 문자라고 생각하면 이해가 쉬움
                if(j === short.length - 1) count++;
            }
        }
        return count;
    }


console.log(strFinder("himamahihelhi", "hi"));