Tag: 알고리즘

이진 탐색(binary search), 자바스크립트로 구현하기

이진 탐색과 구현방법

이진 탐색(binary search)은 데이터 집합에서 원하는 데이터를 찾을 때까지 집합을 이분(二分)하여 탐색하는 방법입니다.

데이터 집합을 둘로 나누고 찾는 데이터가 있는 집합을 선택하여 다시 반으로 나누고 다시 데이터가 있는 집합에 같은 과정을 계속 반복합니다.

따라서 아무리 큰 데이터라도 몇 번의 연산만으로 원하는 데이터를 찾을 수 있습니다.

하지만 이진 탐색은 조건이 있는데요.

데이터가 반드시 순서대로 정렬된 상태여야 합니다.

그림을 통해 탐색의 과정을 확인해 보겠습니다.

위와 같은 데이터 집합에서 2를 찾으려면 먼저 집합을 반으로 나누고 찾는 데이터가 속한 집합을 선택합니다.

그럼 첫 번째로 선택한 집합은 다음과 같습니다.

또 반을 나누고 2가 속한 집합만을 선택합니다.

여기서 반을 나누고 2가 속한 집합을 선택하면 다음과 같습니다.

이제 둘 중 하나를 확인하여 원하는 데이터를 선택하면 됩니다.

이진 탐색 코드는 다음과 같습니다.

const binarySearch=(target, data)=>{

  let low = 0;
  let high = data.length-1;
  
  while(low<=high){
    
    let mid = Math.floor((low+high)/2);    
  
    if(target===data[mid]){
       return mid;
    }else if(target>data[mid]){
      low = mid+1 
    }else if(target<data[mid]){
      high = mid-1
    }
  }

  return undefined;
}

이 탐색 방법은 데이터의 양이 많아지면 엄청난 효율을 자랑합니다.

데이터가 10000까지 있을 때 8000을 찾기 위해서 무차별 대입은 7999번의 연산을 진행해야 하지만 이진 탐색 방법은 13번의 연산이면 원하는 데이터를 찾을 수 있습니다.

자바스크립트를 이용한 BFS, DFS 구현하기(javascript)

데이터는 선형 구조(배열, 연결리스트, 스택, 큐) 또는 비선형 구조(트리, 그래프)로 이루어져 있으며, 순차적으로 나열된 선형 구조에 비해 비선형 구조의 데이터는 탐색이 어렵습니다.

하지만 비선형 구조의 대표적인 탐색 방법인 BFS, DFS를 사용하면 깔끔하게 탐색이 가능합니다.

두 방법 모두 무차별 탐색(Brute Force Search, 모든 데이터를 하나씩 탐색) 방법을 사용합니다.


DFS는 깊이 우선 탐색 방법으로 트리 구조의 데이터에서 노드마다 가장 깊이까지 탐색한 뒤 다음 노드로 이동하는 방법입니다.

위와 같은 트리 구조의 데이터가 있을 때, DFS는 한번 선택한 길은 끝까지 가본 뒤 다음 길을 탐색하는 방식과 같습니다.

그림으로 나타내면 다음과 같습니다.

검색 속도는 BFS에 비해서 느리지만 조금 더 간단합니다.

경로의 특징이 필요한 문제를 풀 때 DFS를 사용합니다. 

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "E"],
  D: ["B", "F"],
  E: ["C","G"],
  F: ["D","H","I"],
  G: ["E","J","K"],
  H: ["F","L"],
  I: ["F", "M"],
  J: ["G","N"],
  K: ["G","O"],
  L: ["H"],
  M: ["I","P"],
  N: ["J"],
  O: ["K"],
  P: ["M"]
};

const bfs = (graph, start) => {

    const checked = [];    // 탐색 완료 데이터
    const willCheck = [];  // 탐색 예정 데이터
    
    willCheck.push(start);
    
    while(willCheck.length!==0){
      const node = willCheck.pop();  // 스택(Last In First Out)
      if(!checked.includes(node)){
       	 checked.push(node);
         //reverse() 제거 시 그림의 4,3,2,1 순서로 탐색     
      	 willCheck.push(...graph[node].reverse());  
        
      }
   }
	return checked;
}

console.log(bfs(graph, "A"));
// ['A', 'B', 'D', 'F', 'H', 'L', 'I', 'M', 'P', 'C', 'E', 'G', 'J', 'N', 'K', 'O']

BFS는 너비 우선 탐색 방법으로 트리 구조 데이터에서 노드의 인접 데이터를 모두 탐색한 뒤 다음 데이터로 이동하는 방법입니다.

그림으로 나타내면 다음과 같습니다.

탐색 속도는 DFS보다 빠르며 최단 거리를 구하는 문제에서 사용할 수 있습니다.

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "E"],
  D: ["B", "F"],
  E: ["C","G"],
  F: ["D","H","I"],
  G: ["E","J","K"],
  H: ["F","L"],
  I: ["F", "M"],
  J: ["G","N"],
  K: ["G","O"],
  L: ["H"],
  M: ["I","P"],
  N: ["J"],
  O: ["K"],
  P: ["M"]
};

const bfs = (graph, start) => {

    const checked = [];
    const willCheck = [];
    
    willCheck.push(start);
    
    while(willCheck.length!==0){
      const node = willCheck.shift(); // 큐(First In First Out)
      if(!checked.includes(node)){
       	 checked.push(node);
      	 willCheck.push(...graph[node]);       
      }
   }
	return checked;
}

console.log(bfs(graph, "A"));
// ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P']