[알고리즘] 브루트포스

| 브루트포스란?

브루트포스(Brute Force)는 말 그대로 '무식하게(force)' '모든 경우를 다 시도(brute)'하는 알고리즘이다.

• 가장 단순하지만, 가장 확실한 방법이기도 하다.

• 예를 들어, 비밀번호가 3자리 숫자라면 000부터 999까지 전부 시도하는 식이다.

• 시간은 오래 걸리지만, 정답을 놓칠 가능성이 전혀 없다.

| 브루트포스의 기본 아이디어

1. 모든 가능한 경우의 수를 만든다.

2. 각 경우가 조건을 만족하는지 검사한다.

3. 그중 최적의 해를 선택한다.

| 예시 : 가장 큰 합을 만드는 조합 찾기

1) 코드

function maxSum(nums) {
  let max = -Infinity;
  
  // 가능한 모든 두 숫자 조합을 비교
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      const sum = nums[i] + nums[j];
      if (sum > max) {
        max = sum;
      }
    }
  }
  return max;
}

console.log(maxSum([1, 5, 3, 2])); // ? 8 (5 + 3)

이 코드는 가능한 모든 두 수의 조합을 다 계산해서 가장 큰 합을 찾는다.

즉, 완전 탐색의 전형적인 예시이다.

2) 브루트포스의 복잡도

• 장점 : 항상 정답을 찾을 수 있다. (보장된 정확도)

• 단점 : 경우의 수가 커지면 시간복잡도가 급증한다.

그래서 문제의 입력 크기(n)이 작을 때만 효과적이며, 보통 n이 1~15 일 때 자주 사용된다.

| 브루트포스를 잘 쓰는 방법

1. 문제 크기를 먼저 파악하자.-> n이 작다면, 브루트포스로 충분히 해결 가능!

2. 중복을 줄이자.-> 정렬, 가지치기, 백트래킹으로 탐색 효율을 높인다.

3. 초기에 아이디어 검증용으로 사용하자.-> 복잡한 알고리즘 구현 전에 기본 로직 확인용으로 유용!

| 마무리

브루트포스는 비효율적이라고 생각하기 쉽지만, 단순함이 곧 강력함일 때가 있다.

복잡한 최적화 알고리즘도 처음에 브루트포스 아이디에어 출발한다.

기초를 이해하면, 그 위에 백트래킹, DFS, DP 같은 고급 알고맂므도 훨씬 쉽게 이해할 수 있다.

다음에는 브루트포스의 발전형 알고리즘인 백트래킹에 대해서 정리해볼 생각이다.