완전탐색

모든 경우의 수를 나열하면서 답을 찾는 방법으로 전체를 하나씩 찾아보기 때문에 Brute-Force라고 한다.

완전탐색 알고리즘

단순 반복문

중첩루프로 모든조합을 탐색하는 방식으로 가장 직관적이고 코드가 간단하지만 하나씩 모든요소를 탐색하기때문에 시간복잡도가 크다

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    // 모든 (i, j) 조합 검사
  }
}

비트마스크

• 이진수 표현을 활용해서, 집합이나 상태를 압축할때 사용, 0 (false) 또는 1 (true)로 원소가 두가지 선택으로 구성이 되어있을때 비트연산자를 활용해서 사용
• 부분집합 , 방문상태, 조합 최적화

비트연산자

• && : And 연산자, 둘다 1 이면 1
• || : OR 연산자 , 하나라도 1 이면 1
• ~ : NOT 연산자, 1 -> 0 , 0 -> 1
• ^ : XOR 연산자, 같으면 0 , 다르면 1
• << , >> : SHIFT 연산자, A << B 는 A 를 B만큼 왼쪽으로 미는것

const arr = ['a', 'b', 'c'];
const n = arr.length;

for (let bit = 0; bit < (1 << n); bit++) {
  let subset = [];
  for (let i = 0; i < n; i++) {
    if (bit & (1 << i)) {
      subset.push(arr[i]);
    }
  }
  console.log(subset);
}

재귀함수

• 재귀 함수를 통해 반복해서 모든 경로를 따라가며 탐색,
• 대표적인 문제 : 피보나치 수열 문제

function fib(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fib(n - 1) + fib(n - 2);
}

// 예시 출력
console.log(fib(6)); // 8

순열

• n개의 원소중에서 순서를 나열해서 m개를 뽑는 모든경우의수, 모든 순서의 대한 조합
• 백트래킹 , 최적화 문제 , 순서 맞추기

function getPermutations(arr, r) {
  const result = [];
  
  //방문한 원소, 중복하지 않게 확인
  const visited = Array(arr.length).fill(false);

  function recur(path) {
  //원하는 순열개수만큼 저장 되면
    if (path.length === r) {
    //결과 배열에 저장
      result.push([...path]);
      return;
    }
	//
    for (let i = 0; i < arr.length; i++) {
   	// 이미 방문한 원소이면 건너뜀
      if (visited[i]) continue;
      //아니면 방문 체크
      visited[i] = true;
      //path에 해당 원소 저장
      path.push(arr[i]);
      //순열 생성 재귀
      recur(path);
      //해당 path 제거 
      path.pop();
      // 방문 제거 
      visited[i] = false;
    }
  }
  recur([]);
  return result;
}
console.log(getPermutations(['A', 'B', 'C'], 2));

!! 시간 복잡도
nPr = n! / (n-r)! -> 완전 탐색이라 n 이 크면 폭발적으로 증가

DFS / BFS

이미지 출처 https://gongbu-ing.tistory.com/58

BFS(Breadth-First-Search) 너비 우선 탐색 : 하나의 노드를 방문하고 그요소에 인접한 같은 level에 있는 모든 노드를 우선 방문하여 탐색
DFS(Depth-First-Search) 깊이 우선 탐색 : 하나의 노드를 방문하고 자식노드를 방문 깊이 먼저 방문하고 그이후 갈곳이 없으면 다른 경로로 탐색

• 길찾기에서 경로를 찾을때 사용

DFS O(V + E)

• 재귀적으로 또는 stack 사용해서 가장 깊게 탐색
• 트리가 아닌 그래프인 경우 어떤 노드를 방문했었는지 여부를 검사하지않으면 무한루프가 된다
• 모든 노드를 방문해야할때 사용
• 경로 탐색, 백트래킹

function dfs(node, graph, visited) {
  visited[node] = true;
  console.log(node);
  for (let next of graph[node]) {
    //방문하지 않았다면 재귀로 더 깊게 탐색
    if (!visited[next]) dfs(next, graph, visited);
  }
}

BFS O(V + E)

• 재귀로 동작하지 않음 반복문 구현.

• 트리가 아닌 그래프인 경우 어떤 노드를 방문했었는지 여부를 검사하지않으면 무한루프가 된다

• 방문한 노드들을 차례로 저장하고 꺼내는 큐 사용

• 최단 경로때, 레벨 탐색 사용

  function bfs(start, graph) {
   const visited = Array(graph.length).fill(false);
   const queue = [start];
  
   //가장 상위는 방문
   visited[start] = true;
  // 현재레벨의 노드들이 방문될때까지 
   while (queue.length) {
     const node = queue.shift();
     console.log(node);
  
     for (let next of graph[node]) {
       //방문하지 않았다면 
       if (!visited[next]) {
         visited[next] = true;
         queue.push(next);
       }
     }
   }
  }