[알고리즘] 완전 검색, 무차별 대입 검색(Brute Force Search)

완전 검색, 무차별 대입 검색(Brute Force Search)

완전 검색은 전체 데이터의 모든 요소를 주어진 조건과 비교하여 원하는 값을 찾아내는

알고리즘 패러다임이다.  

 

컴퓨터 과학(CS)에서 생성 및 테스트라고도 불린다.

 

완전 검색 알고리즘은 코드의 처리 속도보다는 단순 구현이 더 중요한 경우에 사용된다. 즉, 구현하기 간단하며 솔루션이 존재하는 경우에는 항상 솔루션을 찾을 수 있지만, 솔루션의 수가 많을 수록 처리 속도는 길어진다.

 

---

완전 검색, 무차별 대입 검색 알고리즘 조건

이 알고리즘은 3가지의 경우에 적절한 알고리즘이다.

 

1. 문제의 크기가 제한되어 있는 경우.

너무 큰 데이터를 다루는 문제는 조건3의 경우가 아닌 이상 비효율적인 프로그램이 될 수 있다.

 

완전 검색 알고리즘은 데이터의 모든 element 를 하나하나 탐구하는 방식이다. 

즉, '데이터의 수'는 '처리 속도' 와 비례관계를 갖고 있다.

또한 이 알고리즘은 시간복잡도가 데이터의 수에 따라 매우 복잡해질 수 있다.

 

2. 후보 솔루션의 세트를 관리 할 수 있는 사이즈로 줄이는데 사용할 수 있는 문제별 휴리스틱이 있는 경우.

휴리스틱이란?
휴리스틱 (heuristics) 또는 발견법(發見法)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법이다.
- 위키백과

 

결과적으로 조건1의 형태를 만드는게 조건2라고 볼 수 있다. 어떠한 데이터든 그 사이즈를 적당한 크기로 줄여 관리 할 수 있다면

이 알고리즘을 사용하는데 적합한 형태라 할 수 있다.

 

 

3. 처리 속도보다 구현의 단순성이 더 중요한 경우.

 

'처리 속도보다 구현의 단순성이 중요하다.' 라는 말은 다시 말하자면 오차의 최소화를 의미한다.

'완전 검색' 이라는 이름에서 부터 알 수 있듯 이 알고리즘은 모든 데이터를 주어진 규칙에 맞게 탐색한다. 이 말은 즉슨 규칙에 모든 데이터를 하나하나 대입 함으로 이 데이터가 조건에 부합한지 여부를 알 수 있는 것이다.

모든 데이터를 탐색하기에 정확도 100%를 보장하나, 시간은 최대로 든다.

 

그렇다면 완전 탐색 알고리즘이 적용된 문제는 어떤 문제가 있을지 알아보자.

 

---

[백준 2851번] 슈퍼 마리오

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

💡구상

이 문제에서 필요로 하는 조건을 찾아보자.

1. 슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다.
2. 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다. 중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수      없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다.
3. 점수의 합을 최대한 100에 가깝게 만들어야 한다.
4. 주어지는 값은 100보다 작거나 같은 양의 정수이다.
5. 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다.

 

이 문제를 처음 보고 생각한 방식은 element의 총합이 100이상인 경우 N-1 번째 element의 총합과 N번째 element의 총합에서 100을 뺀 값의 절댓값이 100이거나 더 작은 값 혹은 100을 뺀 값의 절댓값이 같은경우에 따라 결과를 출력하는 방식을 생각했다.

하지만, 맞지 않았고 분류된 알고리즘을 확인해보니 완전 탐색법이 사용된 것을 알 수 있었다.

🔍 코드

const score = require("fs").readFileSync("./input.txt", "utf-8").trim().split("\n").map(Number);
let compare = 0;
let offset = 0;
let result = 0;
for (let i = 0; i < score.length; i++) {
  compare = offset;
  offset += score[i];
  if (offset >= 100) {
    if (Math.abs(100 - compare) >= Math.abs(100 - offset)) {
      result = offset;
      break;
    } else if (Math.abs(100 - compare) < Math.abs(100 - offset)) {
      result = compare;
      break;
    }
  }
}
console.log(result);

 

실제로 이 코드를 작동시켜보면 백준사이트에서 제시된 예제 입력3가지를 모두 만족하며 채점할때도 거의 통과할것처럼 채점이 진행된다.

하지만, 이 코드는 백준사이트에서 요구하는 조건을 어디에선가 만족하지 못해 실패로 나온다.

 

offset 변수에 score 배열의 요소를 하나씩 더하며 그 값이 100이상인 경우 비교를 진행해 맞는 조건에 따라 result가 설정되고 반복문이 종료되는 구조이다.

 

실패한 이유가 완전 탐색 알고리즘에 부합하지 않게 구현한 것이 걸린것 이외에 아직 이유를 찾지는 못했지만, 이 문제를 해결하기위해 모든 요소를 탐색하고 차이(diff)가 최솟값(min) 보다 작은 경우 최솟값(min)을 차이(diff)로 업데이트하고 result에는 기존의 result와 offset중 더 큰 값을 저장하여 최종 결과를 보여주는 방식이다.

 

const solution = (score) => {
  let offset = 0;
  let targetScore = 100;
  let min = Number.MAX_SAFE_INTEGER;
  let diff = 0;
  let result = 0;
  score.forEach((e) => {
    offset += e;
    diff = Math.abs(offset - targetScore);
    if (diff <= min) {
      min = diff;
      result = Math.max(result, offset);
    }
  });
  return result;
}
let score = require("fs").readFileSync("./input.txt", "utf-8").trim().split("\n").map(Number);
console.log(solution(score));

 

실제로 동작시켜보면 첫번째 코드는 주어진 예시 input에서 배열을 반복문으로 탐색하다가 100이 되거나 초과한 경우 값을 리턴함으로 반복문을 탈출하여 불필요한 배열탐색을 중지할 수 있다.

 

문제의 타입이 브루트포스 카테고리로 분류되어 있기 때문에 이 알고리즘을 사용해 구현하는 것이 출제 의도에 부합해 보이나 첫번째 코드가 더 효율적이지 않나 라는 생각에 chatGPT에 두 코드의 비교 설명을 요청했다.

 

🤖 chatGPT 응답 정리

두 코드 모두 올바른 결과를 얻을 수 있지만, 첫 번째 코드에서는 100을 초과하는 순간 탐색을 멈추기 때문에 100에 가장 가까운 값을 찾는 데 있어 최적의 결과를 보장하지 못할 수 있습니다. 반면, 두 번째 코드는 합이 100을 초과하더라도 끝까지 계산하여, 모든 가능한 경우 중 가장 100에 가까운 값을 찾기 때문에 더 정확한 해답을 제공합니다.
이것이 사이트에서 두 번째 코드만 정답 처리되는 이유입니다. 전체를 탐색하는 것이 가장 정확한 결과를 보장하기 때문입니다.

 

문제의 원인은 100을 초과하는 순간 탐색의 종료는 최적의 결과를 보장하지 못하기 때문이라고 한다.

하지만, 이 문제는 10개의 버섯이 일렬로 놓여지고, 처음부터 나온 순서대로 집는다는 조건이 있다.

내가 생각하기에는 처음부터 하나씩 탐색을 진행하기 때문에 100을 넘기는 순간 뒤에 나온 숫자들은 '결과에는 영향을 줄 수 없지 않나?' 라는 생각이 들었는데 '혹시 양수여야 하는 조건이 없나?' 하고 다시 읽어 봤지만, 그 입력된 값은 100보다 작거나 같은 양의 정수라는 조건이 있다. 

 

🔥 배운점

정확도가 중요한 프로그램에서 사용할 수 있는 알고리즘에 브루트포스 알고리즘이 있음을 알 수 있었다.

이는 반복문과 조건문을 사용하여 가능한 모든 방법을 단순화하는 기법이다.

이는 완전 탐색에 속하는데 그 완전 탐색에는 백트래킹, 비트 마스크, 순열, 재귀 함수, 깊이 우선탐색(DFS), 너비우선탐색(BFS)가 있었다.