[Algorithm] Search Algorithms (BFS, DFS, Binary Search)

Steve·2021년 5월 16일

BFS Binary Search DFS Search Algorithm algorithm

웹개발 코스

목록 보기

24/59

BFS
DFS
Binary Search

그래프 탐색 (Graph Search)

그래프 탐색은 하나의 정점에서 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것이다. 그래프의 데이터는 배열처럼 정렬이 되어있지 않아 원하는 자료를 찾을 때까지 하나씩 방문하여 찾기 때문이다.

그래프의 모든 정점 탐색에는 여러 방법이 있는데 대표적인 두 가지 방법은 DFS, BFS 이다.
(밑에서 정점은 tree 에서 node로 대체 가능하다.)

Breadth-First Search / Depth-First Search

	BFS	DFS
설명	- 시작 정점에서 가까운 노드부터 탐색을 시작하고, 더 탐색할 노드가 없다면 그 다음 떨어져 있는 정점을 탐색한다. - 넓은 (wide) 탐색.	시작 정점에서 하나의 경로를 끝까지 탐색한 후 찾는 목표가 아니라면 다음 경로로 넘어가 탐색한다. - 깊은 (deep) 탐색.
특징	- 방문할 정점들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. - 그래프 탐색의 경우 어떤 정점를 방문했었는지 여부를 반드시 검사해야 한다. (검사하지 않을 경우 무한루프에 빠질 수 있다.)	- 재귀적으로 동작한다. 스택을 사용할 수도 있다. - 그래프 탐색의 경우 어떤 정점을 방문했었는지 여부를 반드시 검사해야 한다. (검사하지 않을 경우 무한루프에 빠질 수 있다.) - 전위 순회, 중위 순회 등 트리 순회에서 한번에 leaf 노드까지 들어가는 순회는 모두 DFS의 한 종류이다.
장점	- 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로를 보장한다. - 정점의 수가 적고 깊이가 얕을수록 유리하다.	- BFS 에 비해 필요한 저장공간이 적다. (back-tracking 해야하는 노드들만 저장하면 된다) - 찾아야하는 정점이 깊은 단계에 있을수록 유리하다.
단점	- Queue 에 연결된 모든 정점을 저장하기 때문에 공간을 많이 차지한다. - 정점의 수가 늘어날수록 시간이 오래 걸린다.	- 검색을 할 경우 BFS 에 비해 느리다. - 답이 아닌 경로가 매우 깊다면 시간이 오래 걸린다. (그래서 limit 을 걸어두기도 한다.)
시간복잡도	정점을 $V$ 간선을 $E$ 라고 할 경우, - 인접 리스트로 표현된 그래프: $O(V+E)$ - 인접 행렬로 표현된 그래프: $O(V^2)$	정점을 $V$ 간선을 $E$ 라고 할 경우, - 인접 리스트로 표현된 그래프: $O(V+E)$ - 인접 행렬로 표현된 그래프: $O(V^2)$
구현	BFS 를 구현하기 위해서는 queue 가 필요하다. - 각 node 를 enqueue 하고, queue 의 길이가 0 이 될 때 까지 반복한다. (while 사용) Graph BFS 를 위해서는 추가적으로 노드 순회 여부를 저장하는 heap 이 필요하다. - heap 은 node 의 value 값을 키로 갖는다.	재귀적으로 구현한다.
사용	- 비가중치 그래프에서 두 정점 사이의 최단 경로를 찾고 싶을 때 사용한다. - 가중치 그래프에서의 최단 경로 찾기 - 다익스트라 알고리즘 사용.	- 검색이 아닌 순회 (traverse) 할 경우에 많이 쓰인다. (트리 순회 등) - 이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS로 구현하는 것이 좋다.

그래프 BFS, DFS 구현

// 인접 리스트 adjList 를 받았을 때,
// 방문 체크용 배열
let maxVrtx = adjList.length;
const isVisited = new Array(maxVrtx).fill(false);

// BFS (uses queue)
function bfs(adjList, v, isVisited) {
  let q = [v];
  function enQ(v) { q.push(v); }
  function deQ() { return q.shift(); }

  isVisited[v] = true;

  while(q.length > 0){
    let vrtx = deQ(); // 하나 꺼낸다.
    // 정점과 연결된 정점 확인
    for (let i = 0; i < adjList[vrtx].length; i++) {
      // 정점이 있고 방문하지 않았다면
      if (adjList[vrtx][i] && !isVisited[i]) { 
        enQ(i);
        isVisited[i] = true;
      }
    }
  }
}

// DFS (uses recursive)
  function dfs(adjList, vrtx, isVisited) {
    isVisited[vrtx] = true; // 방문 체크
    for (let i = 0; i < adjList[vrtx].length; i++){ 
      // 연결된 버텍스들을 돌면서
      if (!isVisited[adjList[vrtx][i]]){
        // 방문하지 않았다면 방문
        dfs(adjList, adjList[vrtx][i], isVisited);
      }
    }
  }

for (let v = 0; v <= max; v++){
  // 그래프를 순회하려면 모든 정점을 한번씩 돌아보아야한다.
  if (!isVisited[v]){ // 방문하지 않았으면
    // 방문
    // bfs() or dfs() (matrix, i, isVisited)
    //bfs(adjList, v, isVisited);
    dfs(adjList, v, isVisited);
  }
}

Binary Search (이분 탐색)

탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식이다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠르다. 이분 탐색을 하는 방법은 left, right, mid 값으로 탐색하는 것이다. mid의 값은 (left + right) / 2 으로 잡아주고 검색하고자 하는 값과 mid 값을 비교한다.

시간복잡도

전체를 단순히 비교하는 경우 : $O(n)$
이분탐색을 사용할 경우 : $O(log(n))$

순서

탐색할 데이터를 정렬한다.
left, right 으로 mid 값을 잡아준다.
mid 값과 구하고자 하는 값을 비교한다.
비교할 시 mid 값보다 구하고자 하는 값이 높으면 left를 mid + 1로 만들어주고 낮으면 right를 mid - 1로 만들어준다.
left > right 가 될때까지 2~4번을 반복해서 구하고자 하는 값을 찾는다.