Colin's Blog
[Algorithm] 탐색 알고리즘 (Search algorithm)

탐색 알고리즘 (Search algorithm)

알고리즘의 종류중에서도 탐색 및 정렬은 가장 많이 사용되기 때문에 초기에 배워두어야 한다.


검색 엔진은 탐색 알고리즘을 사용한다.

검색의 다른 명칭이 탐색이다.
검색 엔진에는 엔진이라는 이름이 붙어 있는데,
이를 엄밀하게 말하면 원하는 정보를 사람을 대신하여 찾아 주는 데이터 탐색 프로그램이다.
이 데이터 탐색 프로그램에서 사용하고 있는 알고리즘이 바로 탐색 알고리즘이다.


선형 탐색법 (리니어 서치)

선형 탐색법은 매우 간단하다.
왼쪽에서부터 순서대로 하나씩 확인해 나가면 된다.
이는 아무 생각도 요령도 없는 단순한 탐색법이다.
바로 이러한 탐색법이 선형 탐색법이라는 알고리즘이다.

선형 탐색법은 다른 말로 리니어 서치라고도 하는데,
여기서 리니어는 리니어 모터카의 리니어와 같이 일직선이라는 의미를 지니고 있다.
즉, 탐색이 한쪽 끝에서 다른 한쪽 끝으로 나아가는 방식이다.

탐색 시작 -> 결과를 찾을떄까지 루프 반복 -> 결과 찾으면 탐색 종료

찾는 대상이 앞쪽에 있으면, 짧은 시간에 탐색할 수 있지만,
뒤쪽에 있거나 결과가 없거나 혹은 탐색대상이 많으면 많은 시간이 걸리고 비효율적일 수 있다.

단순하고 이해하기 쉽고, 구현하기 쉽지만, 효율은 그다지 좋지않다.
빅오표기법으로 보면 배열의 크기에 따라 시간이 늘어나므로,
O(n)로 볼 수 있다.

// 다음은 배열의 요소중 5인 index를 찾아보는 함수이다.
// 선형 탐색법에 대한 공부중이기에 명확해보이는 함수로 작성해보겠다.

function findIndexLinear(array, condition) {
  for (let i=0; i<array.length; i++) {
    if (array[i] === condition) {
      return i
    }
  }
}

// 최선의 경우 - 한번의 탐색으로 해결
findIndexLinear([2,4,5,1,6], 2)
// 최악의 경우 - 배열의 크기만큼 탐색으로 해결
findIndexLinear([2,4,5,1,6], 6)

선형 탐색법 결론


이진 탐색법은 탐색의 대상인 데이터가
미리 오름차순이나 내림차순으로 정렬되어 있는 경우에 사용할 수 있는 탐색 알고리즘이다.

  1. 가운데에 있는 요소를 먼저 탐색한다.
  2. 조건이 가운데 요소보다 정렬순서가 빠른지 느린지를 보고, 탐색범위를 좁힌다.
  3. 탐색범위를 좁혔으면 다시 한번 가운데를 탐색해본다.
  4. 계속 찾을때까지 반복하여 원하는 결과를 찾으면 탐색 종료.

말이 어렵다면 우리 모두 20살로 돌아가서 술자리에서 게임했던 시절을 떠올려보자.
소주 뚜껑을 가지고 업다운으로 숫자를 맞추었던 경험이 분명히 있을 것이다.
50 -> (25 or 75) -> (12 or 87)

특정된 숫자를 알기위해서 감이 안올때는 범위를 좁히기위해 절반씩 나눈적이 있을텐데
바로 그것이 이진 탐색이다.

가운데 index를 찾기 위해서는 (첫번째 index + 마지막 index)/2를 통해 알 수 있다.
하지만 배열이 홀수가 아닌 짝수라면 가운데인자 공식대로 한다면 소수점이 나올 수 있다.

function findIndexBinary(array, condition) {
    let head = 0;
    let tail = array.length - 1
    // 아래와 같이 배열의 크기가 짝수인 경우에는 3가지 옵션이 있다.
    // 1. 반올림 (Round)
    // 2. 올림 (Ceil)
    // 3. 내림 (Floor)
    // 이번에는 내림을 이용하여 구현을 해보겠다.
    let centerIndex  = Math.floor((head + tail) / 2) // 2.5
    
    while(array[centerIndex] !== condition) {
        // 찾는 결과가 없을 떄 (infinity loop prevent)
        if(head > tail) return '결과를 찾지 못했습니다.'

        if (array[centerIndex] < condition) {
          head = centerIndex + 1;
          centerIndex = Math.floor((head + tail) / 2)
        } else {
          tail = centerIndex - 1;
          centerIndex = Math.floor((head + tail) / 2)
        }
    }

    return `${centerIndex}번째 요소가 일치`
}


findIndexBinary([1,2,4,5,6,7], 7)

선형 탐색법과 비교했을 때 평균적으로 이진 탐색법이 탐색 속도가 더 빠르다.
(물론 선형탐색인데 첫번째 요소가 탐색대상이면 선형 탐색이 더 빠르다.)
(위에서 빠르다고 하는 것은 데이터가 많고 원하는 데이터가 배열의 끝 부분에 저장되어
있는 경우를 말하는 것이다.)

평균적으로 이진 탐색법이 빠르다고 해서 항상 이진 탐색법을 사용하는 것이 좋다는 뜻은 아니다.
데이터의 양과 저장 상황, 정렬 상황에 따라 적절한 알고리즘을 선택해야 한다.

이진 탐색법의 빅오표기는 O(logN)으로 나타낼 수 있다.


앞에서 살펴본 선형 탐새개이나 이진 탐새개법의 전체 조건은 어떤 데이터가 어떤 요소에 들어 있는지
전혀 모르는 상태에서 검색을 시작한다는 것이다.
그러나 해시 탐색법은 데이터의 내용과 저장한 곳의 요소를 미리 연계해 둠으로써 극히 짧은 시간 안에
탐색할 수 있도록 고안된 알고리즘이다.

해시 탐색법은 데이터를 데이터와 같은 첨자의 요소에 넣어 두면 한 번에 찾을 수 있지 않을까?라는
아이디어에서 출발한다.

예를 들어보면 36인 데이터는 첨자 36의 요소에, 48인 데이터는 첨자 48의 요소에 두는 식이다.
하지만 이렇게 2개의 데이터만 저장해도 49개의 요소를 가진 배열이 있어야 한다.
공간적으로 굉장히 낭비가 심해진다.

좀 더 효율적으로 배열을 사용하기 위해 데이터에 일정한 계산을 실시하여,
그 계산 결과값과 같은 첨자를 가진 요소에 보관하는 방법을 생각해보자.

둘 다 12로 나누어진다.
그러면 36은 첨자 3에 48은 첨자 4에 저장할 수 있다.
그럼 5개면 저장이 가능하다.

반드시 어떤 계산을 이용해야 한다는 법은 없지만,
가능한 한 요소 수가 적게 끝나는 계산식이 더 좋다.

좀 더 명확하게 다시 예를 들어보면,
11, 15, 23, 26에 해당되는 숫자를
배열의 크기가 7인 요소에 저장한다면 다음과 같이 할 수 있다.

let arr = new Array(7);
// 어떤 숫자로 나누더라도 7로 나누면 0~6의 숫자가 떨어진다.
// 공의 숫자 % 7 = 공을 넣은 칸의 번호
// 11 % 7 = 4
// 15 % 7 = 1
// 23 % 7 = 2
// 26 % 7 = 5

arr[4] = 11;
arr[1] = 15;
arr[2] = 23;
arr[5] = 26;
// => [ <1 empty item>, 15, 23, <1 empty item>, 11, 26, <1 empty item> ]

이와 같이 어떤 값에 해당하는 다른 값이 산출되는 계산식을 함수라고 한다.
그중에서도 어떤 값이 주어진 경우, 그 값을 대표하는 숫자를 계산하는 함수를 해시 함수라고 한다.
또한 해시 함수의 계산으로 산출된 값을 해시값이라고 한다.
위 예제의 해시값은 공을 넣을 칸의 번호다.

해시라는 단어는 잘게 썬다, 잘게 자른다의 의미이다.
원래의 숫자를 모양이 변할 정도로 가공하여, 전혀 다른 값을 생성한다.라는 의미로 봐도 좋다.

해시 탐색법은 미리 해시 함수를 사용하여 데이터를 저장하는 장소를 정해두어 검색 시간을
놀라울 정도로 단축시킬 수 있다는 장점이 있다.

해시 탐색법을 실현하려면 데이터의 저장 및 검색, 즉 2개의 알고리즘이 필요하다.
먼저 해시 함수를 사용하여 데이터를 저장하는 알고리즘을 알아보자.

// 먼저 배열을 2개 준비하자.

let arrayA = [12,25,36,20,30,8,42]

// 앞에서 배운 2개의 검색 알고리즘(선형 탐색, 이진 탐색)은
// 배열의 요소를 데이터 수만큼 준비하면 충분했지만,
// 해시 탐색법은 이와 달리 저장하는 데이터의 1.5~2배를 준비해야 한다.
let arrayB = new Array(11).fill(0)

// 저장할 요소의 배열을 순회하면서
for (let i=0; i<arrayA.length; i++) {
  // 저장할 공간(첨자)를 계산
  let temp = arrayA[i]%11;
  // 저장할 공간에 데이터가 없으면
  if (!arrayB[temp]) {
    // 저장하기
    arrayB[temp] = arrayA[i]
    // 저장할 공간에 데이터가 있으면
  } else {
    // 데이터가 없는 공간을 찾을때까지
    while(arrayB[temp]) {
      // temp를 증가, 하지만 배열의 크기가 11이므로, 
      // 인덱스가 10을 넘으면(배열의 크기를 넘으면 안되기에) 0으로 변경
      temp < arrayB.length-1 ? temp++ : temp = 0
    }
    // 데이터가 없는 공간을 찾으면 저장
    arrayB[temp] = arrayA[i]
  }
}

// [ 42, 12, 0, 25, 36, 0, 0, 0, 30, 20, 8 ]

저장을 훌륭하게 했다면 이제 탐색하는 알고리즘을 알아보자

// 저장한 데이터와 찾을 요소를 Argument로 넣어준다.
function findHashData(arr, target) {
  // 저장할 공간에 데이터가 있어서 +1해준 경우를 제외하고는
  // 첨자 = 저장할데이터%저장할배열의크기 이다.
  let uniqueValue = target%arr.length;

  // 찾고자 하는 값이 맞을 경우가 나올때까지
  while (arr[uniqueValue] !== target) {
    // 결과가 원하는 값이 아니면, (저장할데이터+1)%저장할배열의크기를 해준다.
    uniqueValue = (uniqueValue+1)%arr.length
  }
  return `저장 위치는 ${uniqueValue}번째 요소입니다.`
}

findHashData(arrayB, 42)
// => '저장 위치는 1번째 요소입니다.'

구현은 기존 탐색법보다 어렵지만, 검색 알고리즘 중에서도 매우 속도가 빠른 알고리즘이므로,
실제 프로그램에서도 많이 사용된다.

해시 탐색법의 빅오 표기법은 O(1)로 나타낼 수 있다.
다만, 해시 충돌이 일어날 경우 O(n)이 될 수 있다.
해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문이다.

© 2018 Colin. All rights reserved.