검색 알고리즘

검색 알고리즘은 컴퓨터 과학에서 필수적인 주제입니다. 데이터를 효율적으로 검색하는 방법을 이해하면 프로그램의 성능을 크게 향상시킬 수 있습니다. 이 글에서는 다양한 검색 알고리즘을 소개하고, 각각의 구현 방법과 시간 복잡도를 설명합니다.

 

목표

• 선형 검색
• 분류된 배열에서의 이진 검색
• 나이브 문자열 검색 알고리즘

선형 검색 소개

선형 검색은 가장 간단한 검색 방법 중 하나입니다. 이 방법은 배열의 각 요소를 순서대로 확인하여 값이 일치하는지 확인합니다. JavaScript에서는 indexOf, includes, find, findIndex와 같은 배열 함수를 사용하여 선형 검색을 수행할 수 있습니다.

한 번에 하나씩 검색하는 이 방법을 선형 검색이라고 합니다.

 

선형 검색 연습

배열과 값을 받아들이고 그 값이 배열 안에 존재하는 경우, 그 인덱스를 반환하는 linearSearch 함수를 작성합니다. 값이 배열 안에 존재하지 않으면 -1을 반환합니다. 이 함수를 구현할 때 indexOf를 사용하지 마세요!

    function linearSearch(index){
  
    }
    
    // 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, val) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === val) {
            return i;
        }
    }
    return -1;
}

// 예시 사용법
console.log(linearSearch([10, 15, 20, 25, 30], 15)); // 1
console.log(linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4)); // 5
console.log(linearSearch([100], 100)); // 0
console.log(linearSearch([1, 2, 3, 4, 5], 6)); // -1
console.log(linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 10)); // -1
console.log(linearSearch([100], 200)); // -1

 

선형 검색 빅오 (Big O)

선형 검색의 시간복잡도는 다음과 같습니다:

• 최선의 경우: O(1) (첫 번째 요소에 있는 경우)
• 최악의 경우: O(n) (마지막 요소에 있는 경우)

따라서 일반적인 시간복잡도는 O(n)입니다. 데이터가 분류되지 않았을 때 사용하는 좋은 방법입니다.

 

이진 검색 소개

이진 검색은 정렬된 배열에서 더 빠른 검색 방법을 제공합니다. 이진 검색은 배열을 절반으로 나누어 검색 범위를 줄여나가는 분할 정복 알고리즘입니다. 이 방법은 정렬된 배열에서만 작동합니다.

 

이진 검색 연습

정렬된 배열과 값을 받아들이고 값이 존재하는 경우 그 인덱스를 반환하는 binarySearch 함수를 작성합니다. 값이 존재하지 않으면 -1을 반환합니다.

function binarySearch(arr, value){}
binarySearch([1,2,3,4,5],2) // 1
binarySearch([1,2,3,4,5],3) // 2
binarySearch([1,2,3,4,5],5) // 4
binarySearch([1,2,3,4,5],6) // -1
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 10) // 2
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 95) // 16
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 100) // -1

 

정답

function binarySearch(arr, elem) {
  let start = 0;
  let end = arr.length - 1;
  let 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;
}

이진 검색 빅오 (Big O)

이진 검색의 시간복잡도는 다음과 같습니다:

• 최선의 경우: O(1) (첫 번째 비교에서 찾은 경우)
• 최악의 경우: O(log N) (반복적으로 반으로 나누는 경우)

따라서 일반적인 시간복잡도는 O(log 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]) {
                console.log("Break");
                break;
            }
            if(j === short.length - 1) {
                count++;
            }
        }
    }
    return count;
}
naiveSearch("lorie loled", "lol"); // 1