검색 알고리즘1- 선형검색, 이진검색

검색 알고리즘

경우1) 문자열이 있는데 해당 문자열에 포함된 다른 문자열이 있는지 확인을 하는 경우

 

경우2) 웹 사이트에 사람들이 가입하고 사용자명을 추가할 수 있게 해서, 사람들이 사용자명(username)과 비밀번호를 입력하고 회원가입 하게는 경우 username이 이미 사용중인 것인지 알려주어야 한다.

let username = [ "Sadye", "Willette", "Nikolos", "Noel", "Sascha", "Brunhilda", "Evie", 
"Evered", "Kennie", "Ashlan", "Sophia", "Cecilio", "Josselyn", "Florrie", "Angela", "Ragnar",
"Robert", "Ennis", "Ephrayim" ]

 

데이터베이스가 없다고 가정해보자. 우선 사용자명이 포함된 배열이 있다고 가정하자. 누군가 양식에 사용자 명을 입력하고 username을 Noel로 비밀번호는 ilovecats72라고 할려고 한다고 생각해보자 이때 사용자가 엔터를 누르면 개발자는 어떤 식으

로든 사용자면이 이미 사용되고 있는지를 확인해야 한다. 

 

let username = [ "Sadye", "Willette", "Nikolos", "Noel", "Sascha", "Brunhilda", "Evie", 
    "Evered", "Kennie", "Ashlan", "Sophia", "Cecilio", "Josselyn", "Florrie", "Angela", 
    "Ragnar","Robert", "Ennis", "Ephrayim" ];

    (()=>{
        console.log(username.indexOf("Noel"));
        //실행결과 3
        console.log(username.indexOf("Noel123"));
        //실행결과 -1
    })();

 

만약에 username목록에 Noel가 있다면 해당 목록에 포함되어 있는지를 어떻게 확인할 수 있을까? 자바스크립트에는 그 작업을 위한 여거가지 내장 함수가 존재한다. 

예를 들면 indexOf를 사용할수 있다. 간단한 함수이다. username.indexOf("Noel")를 실행해보자. Noel이 포함된 경우 index 번호를 없는 username 요소를 대입하면 -1를 반환하는 모습을 확인할 수 있다. 물론 해당 함수 말고도 배열에서 검색할 때 사용할 수 있는 다른 함수들도 존재한다.

 

그러나 이번 섹션에서는 해당 함수가 보이지 않는 곳에서 어떻게 작동하고 있는지 어떻게 해당 함수(내장 메소드)를 자체적으로 구현할 수 있는지, 그리고 어떻게 배열과 문자열에서 검색할수 있는지 얘기한다. 

 

let states = [
  "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", 
  "Delaware", "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", 
  "Kansas", "Kentucky", "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", 
  "Minnesota", "Mississippi", "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire", 
  "New Jersey", "New Mexico", "New York", "North Carolina", "North Dakota", "Ohio", 
  "Oklahoma", "Oregon", "Pennsylvania", "Rhode Island", "South Carolina", 
  "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", "Virginia", 
  "Washington", "West Virginia", "Wisconsin", "Wyoming"
];

 

이번에는 미국의 50개의 주가 요소로 들어 있는 배열을 사용해서 사용자가 자신이 살고 있는 주소에서 state에 해당하는 정보를 제대로 입력하고 있는지 확인한다.

물론 위 배열을 사용하겠지만 어떤 알고리즘을 사용하는 것이 가장 적절한 방법일까? 

 

선형 알고리즘(Linear Search)

인디애나 주 찾기 

const states = [
  "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", 
  "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
  "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", 
  "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", 
  "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon", "Pennsylvania", 
  "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", 
  "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
];

 

사용자가 주소를 입력하려면 주(state)를 입력해야 한다. 우리는 그 주가 애플리케이션의 배령에 포함되어 있는지 확인하려고 한다. 가장 간단한 방법은 모든 개별 항목을 순서대로 살펴보면서 입력받은 값과 배열에 있는 값중에 일치하는 값이 있는지 확인하는 것이다. 

 

따라서 사용자가 인디애나(Indiana)라고 입력하면, 우리는 앞부분 부터 확인을 하기 시작할 것이다.  states 배열의 제일 첫번 째순서인 앨러배마(Alabama)부터 시작해서 순차적으로 인디애나를 찾을 때까지 확인 절차가 계속될 것이다.

그리고 그 과정 중 인디애나를 찾으면 true를 반활할 것이다. 또는 인디애나의 index를 반환한다.

 

만약 인디애나가 state배열에 없으면 배열을 모든 요소를 살펴보게 된다. 그리고 끝부분에는 인디애나를 찾지 못하면 false 또는 -1반환하라는 논리가있다. 

 

사실 이 접근법은 나쁜 접근법이 아니다. 다만 알파벳순으로 분류된 데이터가 있는 상황에서는 더 좋은 방법이 있다. 

 

 

Javascript와 선형검색(lnear search)

let username = [ "Sadye", "Willette", "Nikolos", "Noel", "Sascha", "Brunhilda", "Evie", 
"Evered", "Kennie", "Ashlan", "Sophia", "Cecilio", "Josselyn", "Florrie", "Angela", "Ragnar",
"Robert", "Ennis", "Ephrayim" ]

 

앞서 경우2에서 살펴본 username 배열에는 분류가 되지 않은 상태라, 순서가 아예 없다. 이런 상태에서 어떤 사람이 Angela라고 입력한다고 가정하자 이미 사용중인지 아닌지 어떻게 확인할까? 이럴 경우일 때 가장 좋은 방법이 개별항목을 한번에 하나씩 확인하는 것이다

 

이것을 선형 검색이라고 부르는데 사실 자바스크립트에는 선형 검색기능이 있다. 

위에 나열된 모든 메소드가 보이지 않는 곳에서 같은 작업을 수행한다. 우리가 어떤 항목을 입력하더라도 한 번에 하나의 항복을 확인한다. 즉 index순서대로 검색할 변수와 배열의 요소들을 비교하는 것이다.

 

다만 첫 부분에서 시작해서 끝부분으로 이동하면서 한 번에 하나의 항목을 확인할 수도 있고, 끝부분에서 시작해서 첫부분으로 이동할 수도 있다. 중요한 건 세트 간격으로 이동하면서 한번에 하나의 항목을 확인하는 식으로 모든 항목을 확인하는 것이다. 

 

12 검색 

위 숫자 배열에서 검색을 통해 12를 찾으려고 한다고 가정하자 12가 배열에 포함되는지 확인하는 것이다. 

 

선형검색 pseudocode(의사코드)

• 배열과 변수를 각각 하나 받는 매개변수를 받는 함수를 작성한다. 
  • 이때 함수의 이름은 linearSerch다.
  • 배열 매개변수의 요소는 숫자이다.
  • 변수의 값도 특정 숫자가된다.
• 전체 배열에대한 루프를 만들고 현재 확인 중인 배열 항목 중에 매개변수로 받은 변수와 일치하는 것이 있는지 확인한다.  
• 만약 일치하는 값이 있다면 해당 값의 index를 반환하고, 끝까지 찾을 수 없다면 -1을 반환합니다.

 

선형검색 구현코드

function linearSearchState(checkArray,s){
  for(let i=0; i<checkArray.length; i++){
      if(checkArray[i] === s)return i;        
  }
  return -1;
}


let states = [
    "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", 
    "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
    "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", 
    "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", 
    "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon", "Pennsylvania", 
    "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", 
    "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
  ];

  console.log(linearSearchState(states,"Indiana")); //13
  console.log(linearSearchState(states,"Seoul")); //-1

 

선형검색 시간의 복잡도

배열의 길이인 시간 복잡도(time complexity)가 증가하면, 최악의 경우에 시간이 얼마나 걸릴까?➡️ O(n)이다.

그래서 배열이 길어질수록, 더 많은 검색을 실시해야 한다. 더 많은 연산(operation)을 실시해야한다.

 

만약 마지막 요소인 와이오밍(Wyoming)을 검색하는 중이라면, 연산을 59번해야 한다. 만약 배열의 항목이 5000개인데 그 중에서 마지막 항목을 검색하는 거라면, 각각의 요소 5000개를 확인해야 한다. 즉 배열의 길이가 길어 질수록 n이 증가하고 소요되는 시간도 증가한다. 

 

---

이진알고리즘(Binary Serch)

• 조금 더 빨라진 검색 알고리즘이다.
• 선형 검색에서 했던 것 처럼 한 번에 하나의 항목만 비교대상과 비교하여 제하는 것 보다 훨씬 빠를 수 있다. 이진 검색에서는 확인을 할 때마다 남은 항목의 절반을 없앨 수 있다. 
• 주의할 점은 이진 검색은 분류된 배열을 대상으로만 작동하므로 데이터가 분류되어 있어야한다. 
  • 작은 수 -> 큰수 
  • 큰 수 -> 작은 수
  • 문자열을 알파벳 순서대로 분류

 

미국의 state 검색 

let states = [
    "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", 
    "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
    "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", 
    "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", 
    "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon", "Pennsylvania", 
    "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", 
    "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
  ];

 

위 배열은 이미 알파벳 순서대로 정렬되어 있어 따로 정렬을 할 필요는 없다. 

 

이제 지난번과 같은 예시를 살펴보자. 사용자가 주소를 입력할 때 주(state)를 기재하라고 하고, 그 주가 배열에 있는지 확인 할 것이다. 먼저 넓은 관점에서 보면 위 배열은 비교적 짧은 배열이라는 것을 명심하자. 

 

그래서 사실상 선형검색과 큰 차이를 보이지 않을 것이다. 소요시간에도 큰 차이가 없을것이다. 선형검생에서 이진검색으로 바꿔서 절약되는 시간이 밀리초나 밀리초 미만 즉 1초 이하의 시간이라면 굳이 이진 검색을 사용하는 메리트가 없을 것이다. 하지만 지금은 학습을 위해 또 알파벳 순으로 정렬된 배열의 좋은 예시로 위 배열을 사용하여 이진 검색을 탐구하여 보자. 

 

예제 시나리오

1. 범위 index 0~49

let states = [
    "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", 
    "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
    "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", 
    "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", 
    "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon", "Pennsylvania", 
    "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", 
    "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
  ];

  console.log(states[24]); //Missouri

 

이제 어떤 사용자가 주(state)에 해당하는 필드에 오리건(Oregon)을 입력했다고 가정하자. states 배열이 알파벳순으로 분류가 되어 있기 때문에 이진 검색을 할 때 이 배열의 중간점(halfway point)을 선택한다.

 

50개의 주가 있으므로 정확하게 중간지 점을 가늠할 수는 없고 24번째 주가 대략적인 중간지점이 되어 줄 수 있다. states 배열에 index 24번째의 요소는 미주리(Missouri)다.

 

하지만 우리가 찾을 요소는 오리건이므로 이때 미주리(Missouri)를 기준으로 오리건이(Oregon)의 큰지 작은지 알아야한다. 이때 알파벳 순서 기준으로 오리건이 미주리 전에 있는지 아니면 미주리 다음에 있는디 확인해야 한다. 미주리가 M으로 시작하니까, 오리건은 미주리 다음이다. 

 

때문에 이제는 states배열에 있는 index 25~49 사이에 있는 요소들에만 신경을 써주면 된다. index 24를 포함 이전에 오리건이 있을 확률은 없기 때문이다. 

 

2. 범위 index 25~49

let states = [
   //"Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", 
   //"Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
   // "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", 
   // "Missouri", 
    "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", 
    "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon", "Pennsylvania", 
    "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", 
    "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
  ];

  console.log(states[24]); //Missouri
  console.log(states[37]); //Pennsylvania

 

이제 25~49 index를 반으로 나눠 중간점(halfway point)를 구하면 37번째 요소인를 구하면 펜실베니아(Pennsylvania)가 나오는 것을 확인할 수 있다. 임의적으로 나눈 index 25~49의 배열의 중간점은 펜실베니아이다. 

 

 

펜실베이니아(Pennsylvania)를 기준으로 오리건(Oregon)이 앞에 있는지 뒤에 있는지 가늠해 보면 알파벳상 O는 P다음에 오기 때문에 오리건은 펜실베니아 이전에 있음을 알수있다. 이제 states 배열에서 index 25~36사이에 목록에만 신경을 쓰면 된다. 

 

3. 범위 index 25~36

let states = [
    // "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", 
    // "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
    // "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", 
    // "Missouri", 
    "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", 
    "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon",
    // "Pennsylvania", 
    // "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", 
    // "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
  ];

  console.log(states[24]); //Missouri
  console.log(states[37]); //Pennsylvania
  console.log(states[30]); //New Mexico

 

다시 25~36사이의 중간 지점을 선택한다. 이때 중간점은 31번째 요소가 된다. 대략 30번째 요소의 값을 구하면 New Maxico인것을 확인 할 수 있다. 

 

 

이때 알파벳 순으로 오리건(Oregon)은 N다음에 오게되므로 다시 index 31~36으로 범위를 줄 일수 있다.

 

4. 범위 index 31~36

let states = [
    // "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", 
    // "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
    // "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", 
    // "Missouri", 
    // "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", 
    "New York", "North Carolina", "North Dakota", "Ohio", "Oklahoma", "Oregon",
    // "Pennsylvania", 
    // "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", 
    // "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
  ];

  console.log(states[24]); //Missouri
  console.log(states[37]); //Pennsylvania
  console.log(states[30]); //New Mexico
  console.log(states[33]); //North Dakota

 

다시 31~36사이의 중간 지점을 선택한다. 이때 중간점은 33번째 요소가 된다. 대략 33번째 요소의 값을 구하면 노스 다코타(North Dakota)인것을 확인 할 수 있다.

이때 아직 N보다 오리건주는 뒤에 있을 것이므로 범위가 34~36으로 좁아진다.

 

4. 범위 index 31~36

let states = [
    // "Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut", "Delaware", 
    // "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas", "Kentucky", 
    // "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan", "Minnesota", "Mississippi", 
    // "Missouri", 
    // "Montana", "Nebraska", "Nevada", "New Hampshire", "New Jersey", "New Mexico", 
    // "New York", "North Carolina", "North Dakota",  
     "Ohio", 	  //index - 34
     "Oklahoma",  //index - 35
     "Oregon",	  //index - 36
    // "Pennsylvania", 
    // "Rhode Island", "South Carolina", "South Dakota", "Tennessee", "Texas", "Utah", "Vermont", 
    // "Virginia", "Washington", "West Virginia", "Wisconsin", "Wyoming"
  ];

  console.log(states[24]); //Missouri
  console.log(states[37]); //Pennsylvania
  console.log(states[30]); //New Mexico
  console.log(states[33]); //North Dakota

 

이제 남은 34, 35, 36의 index에 해당하 하는 값들의 중간 값은 index 35번의 값인 오클라호마(Oklahoma)이다. 알파벳 순으로 모면 오클라호마와 오리건은 같은 O로 시작하지만 두번째 알파벳이 각각 K와 R로 오리건이 오클라호마 뒤에 순서해 index 36번에 위치하고 있음을 알 수 있다. 

 

정리

위 예시는 많은 작업이 필요해 보이지만, 선형 검색을 사용해서 맨 처음부터 확인을 할 때와 비교해 보면 5번의 횟차의 추측으로 값을 발견할 수 있었다. 즉 데이터가 분류된 상태라면 이진 검색으로 시간을 많이 절약할 수 있다. 

 

이진검색의 구현 : 분할 정복(Divide and Conquer)

이진검색의 기본적인 개념은 분할정복이다. 보통 배열의 중간에 있는 중간지점을 선택하고 임의적으로 배열을 두 부분으로 나눈다. 그리고 찾는 값이 중간점을 기준으로 좌측 절반과 우측 절반 중 어느 쪽에 있을지 확인한다.

 

이런 분할정복에서 잊지 말아야하는 중요한 점은 데이터가 정렬되어 있어야 한다는 것이다. 그래서 분류된 숫자나 문자열 배열 같은 게 있는 경우에, 한 숫자/문자가 다른 숫자/문자보다 큰지/뒤에 있는지, 아니면 작은지/앞에 있는지를 쉽게 비교할 수 있다면 이진 검색을 구현할 수 있고 원하는 값을 더 쉽게 찾을 수 있다. 

 

 

이진검색 pseudocode(의사코드)

• 이진검색을 구현할 함수는 정렬된 데이터를 받는다.
• 2개의 변수를 만들어야 한다.
  
  • left pointer :  계산을 시작하는 좌측을 나타내는 포인터
  • right pointer :  배열의 길이에서 -1을 한 값 
• 왼쪽 포인터가 오른쪽 포인터를 만나기 전까지 다음 과정을 반복한다. 
  • 중간 값을 가르키는 포인터를 만든다.
  • 찾고 있는 값과 일치하는 값에 도달하면 해당 중간 index 리턴한다.
  • 중간 값이 찾는 값보다 작으면 왼쪽 포인터를 오른쪽으로 이동시킨다.
  • 중간 값이 찾는 값보다 크면 오른쪽 포인터를 왼쪽으로 이동시킨다. 
• 연산을 다 끝낸 후에도 값을 찾지 못하면 -1을 반환한다.

 

이진검색 구현코드

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

    while(right != left){
        if(arr[middle] === findOne) return middle;
        if(arr[middle] > findOne){
            right = middle;
            middle -= Math.ceil((right - left)/2)
        }

        if(arr[middle] < findOne){
            left = middle; 
            middle += Math.ceil((right - left)/2) 
        }
    }

    return -1;
}

 

 

 

 

[출처 - JavaScript 알고리즘 & 자료구조 마스터클래스 - 저, ColtSteele]

https://www.udemy.com/course/best-javascript-data-structures