[Algorithm] 브루트 포스(Brute Force) 알고리즘이란?

각 단어와 브루트 포스라는 단어의 사전적 정의는 아래와 같다.

 

Brute : 짐승, 신체적인 힘(폭력)에만 의존하는
Force : 물리력, 폭력 / (물리력을 이용해서) 억지로 ~~하다
Brute Force : 억지 기법(무차별 대입해 억지로 문제를 푸는)

 

모든 방법을 다 동원해서 답을 찾는 알고리즘이라 생각된다.

아래는 위키백과에서 설명하는 브루트 포스 알고리즘이다.

 

https://en.wikipedia.org/wiki/Brute-force_search

Brute-force search - Wikipedia

무차별 검색(brute-force search) 또는 철저한 검색(exhaustive search)은 생성 및 테스트라고도 하며 가능한 모든 후보를 체계적으로 검사해서 각 후보가 문제를 만족하는지 여부를 확인하는 매우 일반적인 문제 해결 기법이자 알고리즘 패러다임이다...(중략)...무차별 대입 검색은 구현이 간단하고 솔루션이 존재하는 경우 항상 솔루션을 찾을 수 있지만 구현 비용은 후보 솔루션의 수에 비례하며, 많은 실제 문제에서 문제 크기가 증가함에 따라 매우 빠르게 증가하는 경향이 있다. 따라서 무차별 대입 검색은 일반적으로 문제 크기가 제한돼 있거나 후보 솔루션 집합을 관리할 수 있는 크기로 줄이는 데 쓸 수 있는 문제별 휴리스틱이 있을 때 사용된다. 이 방법은 처리 속도보다 구현의 단순성이 더 중요한 경우에도 쓰인다
무차별 대입 검색은 다른 알고리즘이나 메타 휴리스틱을 벤치마킹할 때 기준이 되는 방법으로도 유용하다. 실제로 무차별 대입 검색은 가장 단순한 메타 휴리스틱으로 볼 수 있다

가장 큰 단점은 실제 문제의 경우 후보 수가 엄청 많다는 것이다. 데이터 크기 증가에 따라 후보 수가 급격히 증가하는 현상은 모든 종류의 문제에서 발생한다. 10개 글자의 특정 재배열을 찾는 경우 10!인 3,628,800개의 후보를 고려해야 하지만 20글자의 경우 후보는 2.4경에 달하며 검색에 약 10년이 소요된다. 이런 현상을 조합 폭발 or 차원의 저주라고 부른다

무차별 대입 알고리즘의 속도를 높이는 한 가지 방법은 문제 클래스에 맞는 휴리스틱을 사용해서 검색 공간(후보 솔루션의 집합)을 줄이는 것이다

 

모든 경우의 수를 따져서 문제의 해결법을 찾는 알고리즘이다. 가장 일반적이라고 하지만 역시 따져야 하는 경우의 수가 많을수록 그만큼 시간이 오래 걸리는 건 어쩔 수 없다.

이 알고리즘의 속도를 개선하려면 당연히 경우의 수를 줄이는 것을 고려할 수 있다.

다른 곳에선 어떻게 설명하는지 확인한다.

 

https://www.freecodecamp.org/news/brute-force-algorithms-explained/

Brute Force Algorithms Explained

0~9까지 4자리 숫자가 있는 자물쇠가 있는데 비밀번호를 잊어서 무차별 암호 대입 방법을 사용해 자물쇠를 열어야 한다. 모든 숫자를 0으로 설정하고 0001, 0002와 같이 하나씩 시도한다. 최악의 경우 10,000번 시도해야 조합을 찾을 수 있다...(중략)...무차별 대입 방식은 가능한 모든 경로의 총 거리를 계산한 다음 가장 짧은 경로를 선택하는 것이다. 이 방법은 영리한 알고리즘을 통해 가능한 많은 경로를 제거할 수 있어서 효율적이지 않다
무차별 대입의 시간 복잡도는 O(mn)이다. 따라서 무차별 대입을 통해 m개의 문자열에서 n개의 문자로 이뤄진 문자열을 검색하려면 n * m번의 시도가 필요하다

 

https://www.geeksforgeeks.org/brute-force-approach-and-its-pros-and-cons/

Brute Force Approach and its pros and cons - GeeksforGeeks

무차별 대입 알고리즘은 문제의 답을 찾을 때까지 모든 옵션을 체계적으로 탐색하는 간단하고 포괄적인 검색 전략이다. 심층적인 조사가 가능할 정도로 문제가 작을 때 쓰이는 문제 해결법이다. 그러나 시간 복잡도가 높기 때문에 대규모 문제에는 비효율적이다

< 무차별 대입 알고리즘의 특징 >

- 주어진 문제에 대해 가능한 모든 방법을 열거하는 직관적, 간접적, 간단한 문제 해결법이다
- 가까운 시장으로 가는 모든 경로를 탐색해서 최소 최단 경로를 찾는 등 일상에서 많은 문제를 해결할 수 있다
- 선반 공간을 최적화하기 위해 모든 가능성을 써서 선반에 책을 배열하는 등의 문제도 마찬가지다
- 최적화 알고리즘도 가능하지만 일상 생활 활동은 무차별 대입 방식을 사용한다

< 장점 >

- 모든 후보 솔루션을 나열해서 올바른 솔루션을 찾는 게 보장된 방법이다
- 일반적인 방법이고 특정 문제 영역에 한정되지 않는다
- 작고 간단한 문제를 풀 때 이상적이다
- 단순성으로 유명해서 비교 벤치마크로 사용할 수 있다

< 단점 >

- 비효율적이다. 실시간 문제의 경우 종종 O(N!)을 넘는 경우가 많다
- 좋은 알고리즘 설계보다 문제 해결을 위해 컴퓨터 시스템 성능을 타협하는 데 더 많이 의존한다
- 느리다
- 다른 설계 패러다임을 사용해 구축된 알고리즘에 비해 건설적이거나 창의적이지 않다

 

다른 곳에서도 위 내용들과 크게 다르지 않은 내용들을 설명하니 마무리한다.

아래는 브루트 포스 알고리즘의 예제다.

 

fun main() {
    val text = "ABCDEF"
    val pattern = "EF"
    val result = bruteForceSearch(text, pattern)

    if (result != -1) {
        println("패턴이 문자열에서 $result 위치에 있습니다.")
    } else {
        println("패턴을 찾을 수 없습니다.")
    }
}

fun bruteForceSearch(text: String, pattern: String): Int {
    val n = text.length
    val m = pattern.length

    for (i in 0 .. (n - m)) {
        var j = 0
        while (j < m && text[i + j] == pattern[j]) {
            j++
        }
        if (j == m) {
            return i
        }
    }
    return -1
}

// 패턴이 문자열에서 4 위치에 있습니다.

 

ABCDEF 문자열에서 EF가 어느 인덱스에서 등장하는지 찾는 예시다.

text 문자열의 처음부터 끝까지 for문으로 반복하며 pattern 변수의 값(EF)과 일치하는 부분 문자열을 찾는다. 중단점을 걸어서 어떤 순서로 동작하는지 확인해보자.