[알고리즘] 브루트포스 알고리즘

브루트포스 알고리즘

- 직관적이고 무식한 알고리즘
- 모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과만을 가져오는 방식
- 모든 영역을 전체 탐색하는 알고리즘
- 수가 커질수록 시간복잡도가 엄청나게 증가

순차 탐색(선형구조 탐색)

선형구조를 탐색할 때 사용하며, 배열이나 연결리스트, 스택등이 있다.
탐색할 범위가 적을 때 사용한다.
ex) 크기가 n인 배열이 존재한다면, n번 탐색을 한다.

탐색순서는 아래와 같다.

1) 주어진 문제를 선형구조로 구조화하기
2) 구조화된 문제 공간을 적절한 방법으로 해를 구할 때까지 탐색
3) 구성된 해를 정리

그래프 탐색(비선형구조 탐색)

비선형구조를 탐색할 때 사용하는 방법으로
크게 DFS(깊이 우선 탐색)과 BFS(넓이 우선 탐색)로 나눌 수 있다.

브루트포스 알고리즘 문제 풀이

브루트포스 알고리즘을 사용하여 백준 2798번: 블랙잭을 풀이하였다.

/**
 * 백준 알고리즘 2798 블랙잭
 * 브론즈 2
 * 브루트포스 알고리즘
 * **/

const readline = require("readline");
const solution = (input) => {
  let M = Number(input.shift().split(" ")[1]); // 딜러가 외친 숫자 M
  let arr = input[0].split(" ").map((num) => Number(num));
  let length = arr.length; // 주어진 N장의 카드
  let sum = 0; // 임시 저장을 위한 공간
  let maxSum = 0; // 최대합을 저장할 공간

  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      for (let k = j + 1; k < length; k++) {
        sum = arr[i] + arr[j] + arr[k];
        if (sum <= M && sum >= maxSum) {
          maxSum = sum;
        }
      }
    }
  }

  return maxSum;
};

let input = [];
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  input.push(line);
  if (input.length === 2) {
    console.log(solution(input));
  }
});