[알고리즘] 브루트 포스(brute force) - 완전(전체) 탐색

완전 탐색이란 가능한 모든 경우의 수를 모두 탐색하며 조건에 충족되는 결과만 가져오는 기법이다. 

---

✔️ 브루트 포스 장점

알고리즘을 설계하고 구현하기가 쉽다.

모든 범위를 다 탐색하기 때문에 무조건 정답을 찾을 수 있다.

복잡한 알고리즘 없이 빠르게 구현이 가능하다.

---

✔️ 브루트 포스 단점

인력값이 커질 경우, 알고리즘의 실행 시간은 매우 오래 걸릴 수 있다.

메모리의 효율면에서 매우 비효율적이다.

---

✔️ 브루트 포스 종류

• 선형 구조 : 순차 탐색
• 비선형 구조 : 백트랙킹, DFS, BFS

---

✔️ 브루트 포스 예시 문제

아래와 같은 숫자배열이 존재할 때, 숫자의 각자릿수의 합이 가장 큰 수를 출력하는 문제가 있다고 하자.

(단, 각 자릿수의 합이 같다면, 기존 숫자가 더 큰 값을 출력 -> 345, 543이라면 543을 출력)

let arr = [134, 245, 345, 543, 163]

const solution = (cnt, arr) => {
    let idx = 0;
    let max = 0;
    for (let i = 0; i < cnt; i++) {
      let num = arr[i];
      let sum = 0;
      while (num) {
        sum += num % 10;
        num = ~~(num / 10);
      }
      console.log(sum);
      if (max < sum || (max === sum && arr[idx] < arr[i])) {
        idx = i;
        max = sum;
      }
    }
    return arr[idx];
  };

  let arr = [134, 245, 345, 543, 163];
  console.log(solution(7, arr));

참고

https://foreverhappiness.tistory.com/104

[알고리즘 - 기초] 완전 탐색, 브루트 포스 (Brute Force)

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/