브루트 포스

개론

---

브루트 포스(Brute force)는 정말 단순히 직역하면 짐승의 힘, 엄청난 힘 정도로 번역된다.

허나 제대로 번역하면 무차별 대입이라는 뜻이 나오게 된다.

그렇다고 엄청난 힘이 완전히 틀린 말은 아니다.

브루트 포스 알고리즘은 짐승들이 압도적인 힘으로 상대를 찍어누르듯, 엄청난 양의 데이터를 전부 대입해보는 알고리즘을 말하기에 압도적이라는 면에서는 비슷한 의미로 쓰이게 된다.

 

다른 말로 쉽게 말하면 전수 조사라고도 할 수 있다.

하지만 문제는 엄청난 양의 데이터를 어떻게 구할 것인가? 이다.

대입해 볼 데이터를 구해줄 사람은 없다.

즉, 브루트 포스 알고리즘은 단순히 데이터를 대입만 하는게 아니라 직접 데이터를 구해서 확인해보는 과정을 말한다.

 

 

브루트 포스 문제의 접근 방법

---

브루트 포스 문제의 접근 방법은 굉장히 쉽다.

답이 될 수 있는 모든 경우를 확인해보는 것이다.

 

가장 원초적이고, 직관적인 해결 방법이다.

따로 생각할 필요없이 다 해보면 답이 나오기 때문에 접근법으로 머리를 싸맬 필요가 없다.

하지만 브루트 포스 외의 다른 알고리즘들이 나온 이유는 다들 알다시피, 규모가 커질수록 브루트 포스는 현실적이지 못하기 때문이다.

그렇기에 브루트 포스를 이용할 때는 전체 규모가 어느 정도인지 가늠해보고 사용해야한다.

이렇게 말하면 정말 쉽지만, 사실 답이 될 수 있는 모든 경우를 구하는 것이 진짜 접근 방법이다.

모든 경우를 구하기 위해서는 탐색이 필수적으로 들어가게 되는데, 이 탐색법에 따라 브루트 포스의 효율성이 갈리게 된다.

어떤 자료형을 쓰고, 어떤 상황에 처해있느냐에 따라 탐색법이 조금씩 바뀌겠지만, 대체로 자료구조에 맞게 탐색하면 빠르게 전체를 검사해볼 수 있다.

그래서 대표적인 두 탐색법에 대해서 이야기를 해보겠다.

 

순차 탐색

처음부터 하나씩 검사한다.

 

 

순차 탐색은 선형 구조를 탐색할 때 사용하는 탐색법이다.

이름 그대로 앞에서부터 뒤까지 순서대로, 순차적으로 탐색하는 방법을 말한다.

배열, 연결리스트, 스택 등등에서 이 방식으로 탐색을 한다.

찾으려는게 하나고 배열의 크기가 N이라면 N번만 탐색하면 해결이 되지만,

만약에 찾으려는것도 N개에 배열의 크기도 N이라면 탐색 횟수가 N^2이 된다.

찾는 것과 배열이 커지면 커질수록 배가 되어 커지므로, 크기가 큰 배열에서는 비효율적인 탐색법이 된다.

하지만 굉장히 쉽게 구현할 수 있으므로 적은 범위 내에서는 이 방식을 많이 사용한다.

 

그래프 탐색

깊이 우선인지 너비 우선인지를 생각해보자

 

 

비선형 구조를 탐색할 때 사용하는 탐색법으로 크게 BFS와 DFS로 나눠진다.

이 두 탐색법의 의미는 각각 너비 우선 탐색과 깊이 우선 탐색이라는 뜻으로 너비를 중점으로 탐색하냐 또는 깊이를 중점으로 탐색하냐에 따라 두 탐색법으로 나눈다.

두 탐색법의 작동 과정은 그래프 알고리즘에서 설명하는 것으로 하겠다.

 

마무리

---

브루트 포스 알고리즘은 모든 경우의 수를 다 확인해보는 알고리즘이다.

모든 경우의 수를 효율적으로 구하는게 관건이다.

선형 구조에서는 순차 탐색을 이용하면 효율적이고,비선형 구조에서는 그래프 탐색과 같은 탐색법을 이용하면 효율적이다.