Udemy - 탐색 알고리즘

---

탐색(검색) 알고리즘이란?
쉽게 설명하자면, 특정한 배열, 또는 객체 등에 존재하는 특정값을 찾아내는 알고리즘이다.

탐색 알고리즘의 종류

1. 선형 탐색
2. 이진 탐색
3. 순수 탐색
4. KMP String 탐색

---

📏  선형 탐색 (Linear Search)

배열 내에 존재하는 값들을 하나씩 체크하며 검색해 나가는 방식의 탐색 알고리즘이다.

1. Array.indexOf()

   • 시간복잡도는 O(N)으로, 반복문 안에서 사용에 주의해야 한다.
   • 해당 값이 존재하면 해당 값의 가장 선두에 있는 index값을 반환해준다.
   • 해당 값이 존재하지 않으면 -1을 반환한다.

2. Array.includes()

   • 시간복잡도 : O(N)
   • 특정 값이 존재하면 true를, 존재하지 않으면 False를 반환

3. Set.has()

   • 시간복잡도 : O(1)
   • Array.includes()와 비슷하지만, 이는 배열이 아닌 set에서 사용하는 함수다.
   • const OOO = new Set() 을 통해 Set을 생성할 수 있고, set에는 중복값을 담을 수 없다.

4. 기본 예제

   주어진 숫자의 index값을 찾는 탐색 알고리즘을 작성하시오 : O(N)

   

   function linearSearch(arr, target) {
     for (let i = 0; i < arr.length; i++) {
       if (arr[i] === target) {
         return i;
       }
     }
     return -1;
   }

5. 선형 탐색의 BIG O

   • O(1) : 베스트 👍
   • O(N) : 평균 or 워스트 👎
     ⇒ 배열의 길이가 1만개라면, 1만번의 탐색을 수행해야 함, 하지만 일반적인 경우에는 그리 최악은 아님

---

📖  이진 탐색 (Binary Search)

선형 탐색보다 훨~~씬 빠른 탐색 알고리즘이다.
이전에 잠깐 맛만 봤던 “분할 점령 패턴”의 실질적인 활용 예라고 보면 된다.

⚠️ 배열이 정렬되어 있는 경우에만 사용 가능하다..

1. 기본 로직

   • 배열을 절반으로 쪼갠다
     ⇒ 진짜 배열을 slice하는건 아니고, 이중 포인터를 사용한다
   • 중간값을 기준으로 좌측을 잘라낼지, 우측을 잘라낼지 결정하도록 한다.

2. 기본 예제 코드

   이진 탐색 방식으로 주어진 숫자의 index값을 반환하는 알고리즘을 작성하시오.

   

   function binarySearch(arr, target) {
     // left와 right 포인터를 선언
     let left = 0;
     let right = arr.length - 1;
     // 초기 값에 대한 중간값(middle) 선언
     let middle = Math.floor((left + right) / 2);
     // 중간값이 target과 같아지거나, left가 right보다 커지면 반복문 종료
     while (arr[middle] !== target && left <= right) {
       target < arr[middle] ? (right = middle - 1) : (left = middle + 1);
       middle = Math.floor((left + right) / 2);
     }
     return arr[middle] === target ? middle : -1;
   }

3. 이진 탐색의 BIG O

   • O(1) : 베스트 👍
   • O(logn) : 기본 ☺️

---

🍼  순수 탐색 (Naive String Search)

어떤 String에 특정한 subString이 포함되는지 탐색하는 알고리즘
ex) “my name is hoonjoo”에 “hoon”이 포함되는가?

💡 원래는 String.includes() 를 사용하면 되지만, 순수 탐색 방법을 활용하면 첫 글자를 비교 → 같으면 두 번쨰 글자를 비교 / 다르면 비교대상의 첫 글자 인덱스를 우측으로 이동

1. 기본 예제 코드

   주어진 target String이 기준 String에서 몇 번 나타나는지 반환하는 순수 탐색 알고리즘 코드를 작성하시오.

   function naiveSearch(base, target){
       let count = 0;
       for(let i = 0; i < base.length; i++){
           for(let j = 0; j < target.length; j++){
              target[j] !== base[i+j] && break;
              j === target.length - 1 && count++;
           }
       }
       return count;
   }

---