Brute Force (완전탐색)

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

---

 우리가 완전탐색이라고도 부르는 브루트 포스 알고리즘은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 엄청난 시간이 걸리는 데다 자원이 엄청나게 들어 무식한 방법이라고 할 수 있지만 100%로 완전 탐색할 수 있다는 장점이 있다. 이론적으로 가능한 모든 경우의 수를 다 검색하보는 것이라 암호학에서는 가장 확실한 방법으로 통용되고 있다.

 

 브루트 포스는 크게 선형 구조와 비선형 구조로 나눌 수 있다.

• 선형 구조: 순차 탐색
• 비선형 구조: 백트래킹, DFS, BFS

 우리는 이런 구조를 가지고 많은 알고리즘 문제를 해결해야 한다. 그러므로 우리는 이런 구조에 대한 이해를 확실하게 해서 해당하는 알고리즘 문제에 가장 알맞은 구조를 사용해 문제를 해결해야 할 것이다.

 

 

순차 탐색

---

 순차 탐색은 리스트에서 특정한 값을 순차적으로 탐색하여 찾는 알고리즘이다. 이 알고리즘은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것이다. 검색한 리스트에 길이에 따라서 시간이 오래걸리기 때문에 리스트의 길이가 길면 비효율적이지만, 가장 단순하여 구현이 쉽고 리스트의 정렬이 필요가 없다는 장점이 있다. 

 우리가 가장 단순하게 많이 사용하는 알고리즘이지만, 시간 초과가 많이 발생함으로 해당 알고리즘을 최소화할 필요가 있다.

 

순차 탐색을 Kotlin으로 간단하게 작성해 보겠다.

 

fun main() {
    val array = arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9)
    println(sequential_search(4, array))
}

fun sequential_search(target: Int, array: Array<Int>): Int {
    for (i in array) {
        if (array[i] == target)
            return i
    }
    return 0
}

 

 이 코드는 배열에서 target 숫자의 index 번호를 찾는 문제이다. 만약 해당 target번호가 배열의 마지막에 위치한다면 최악 시간 복잡도는 O(N)이 된다.

 

나머지 비선형 구조는 다른 게시글에서 다뤄보도록 하겠다.

 

Reference

브루트 포스 - 나무위키

 

순차 검색 알고리즘 - 위키백과, 우리 모두의 백과사전