완전 탐색 브루트 포스 알고리즘

ℹ️ 브루트 포스 (Brute Force)

: (정제되지 않은) 난폭한 힘

- 가능한 모든 경우의 수를 탐색하여 문제를 해결하는 방식

- 가능한 모든 조합을 시도해 답을 찾는 방법

 

*️⃣ 특징

1. 단순하고 직관적: 특정한 규칙이나 최적화 없이 가능한 모든 경우를 무작정 탐색
2. 알고리즘 설계가 쉬움: 모든 경우를 시도하는 방법으로 단순하다
3. 시간 복잡도: 일반적으로 시간이 많이 소요된다. 경우의 수가 많아질수록 수행 시간이 기하급수적으로 늘어난다.

☑️ 장점

 

• 적용이 간단: 복잡한 알고리즘 설계나 최적화 없이 쉽게 적용할 수 있다.
• 문제 해결 보장: 경우의 수를 모두 확인하므로, 정확도 100%를 보장한다.

☑️ 단점

 

• 비효율적: 경우의 수가 많은 문제에 대해서는 수행 시간이 오래 걸리며, 비효율적인 메모리 사용과 CPU 사용이 발생한다.
• 시간 복잡도가 높음

 

 

*️⃣ 관련 알고리즘 문제 (JavaScript)

백준 2503번 - 숫자 야구

https://www.acmicpc.net/problem/2503

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 풀이
function solution(arr) {
  const N = +input[0];
  const game = [];

  for (let i = 1; i <= N; i++) {
    const [guess, strikes, balls] = arr[i].split(' ').map(Number);
    game.push({ guess: guess.toString(), strikes, balls });
  }

  let count = 0;

  // 123부터 987까지 모든 경우 탐색 (숫자가 겹치지 않는 세 자리 수)
  for (let num = 123; num <= 987; num++) {
    const numStr = num.toString();
    if (new Set(numStr).size < 3 || numStr.includes("0")) continue; // 숫자가 겹치거나 0이 포함된 경우 스킵

    // 각 입력 조건을 모두 만족하는지 확인
    let isValid = true;
    for (const { guess, strikes, balls } of game) {
      if (!checkCondition(guess, numStr, strikes, balls)) {
        isValid = false;
        break;
      }
    }

    // 모든 조건을 만족하면 카운트 증가
    if (isValid) count++;
  }

  return count;
}

// 숫자가 조건에 맞는지 체크하는 함수
function checkCondition(guess, number, strikes, balls) {
  let strikeCnt = 0;
  let ballCnt = 0;

  for (let i = 0; i < 3; i++) {
    if (guess[i] === number[i]) {
      strikeCnt++;
    } else if (number.includes(guess[i])) {
      ballCnt++;
    }
  }

  // 모두 같으면 true 반환
  return strikeCnt === strikes && ballCnt === balls;
}

console.log(solution(input));