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

알고리즘

chan10 2021. 5. 20. 14:10

Brute Force : Brute(무식한) + Force(힘)

브루트 포스 알고리즘은 문제를 해결하기 위한 모든 경우의 수를 탐색하면서 요구 조건에 맞는 결과를 얻는 방식입니다.

이렇게 모든 방법을 찾아보는 알고리즘을 완전탐색 알고리즘이라고 합니다.

브루트 포스 알고리즘은 구현하기도 쉽고 모든 경우의 수를 다 찾아보기 때문에 무조건 정답을 찾을 수 있습니다.

그러나 모든 경우의 수를 다 찾아보는 만큼 시간, 메모리 사용면에서 비효율적인 부분을 가지고 있기에 시간 복잡도는 주로 O(N!), O(2^N)입니다.

알고리즘 설계의 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 것입니다.

그러기 위해 먼저 문제 해결에 필요한 모든 자료를 구조화한 후 전체 탐색을 할 수 있어야합니다.

선형구조를 모두 탐색하는 방법은 순차 탐색이 있습니다.

비선형 구조를 모두 탐색하는 방법은 깊이 우선 탐색(DFS, Depth First Search), 너비 우선 탐색(BFS, breadth first search)이 있습니다.

* 너비 우선 탐색은 브루트 포스, 깊이 우선 탐색은 백트래킹과 관련이 깊습니다.

1. 주어진 자료를 선형 구조로 구조화한다. (구조화)

2. 구조화된 자료들을 구조에 맞는 방법으로 해를 구할 때까지 탐색한다. (탐색)

3. 탐색한 해를 주어진 출력형식에 맞게 정리한다. (정리)

브루트 포스 알고리즘을 구현하는 방법으로는 반복문, 재귀 함수를 이용하여 구현할 수 있으나 주로 재귀를 사용합니다.

반복문의 경우 문제가 복잡할수록 코드가 길어지는 단점이 있습니다. 재귀 함수를 사용하면 코드를 깔끔하고 유연하게 작성할 수 있으며 더욱 직관적으로 보여질 수 있습니다.

반복문을 이용한 Brute Force 예시

for(int i=0; i<n; i++) {
  for(int j=i+1; j<n; j++)  {
    for(int k=j+1; k<n; k++) {
      ... (r개의 for문..)

재귀를 이용한 Brute Force 예시

for(int i =0; i <n; i++) {
    pick(n,r-1);
    ..
  }
void pick(int n, int r) {
  if(r==0) {
    return;
  }
  ..
}

r의 크기가 증가할수록 for문을 더 많이 작성해야 합니다. 그러나 재귀함수는 r의 크기가 증가해도 변경이 없기에 코드를 더욱 유연하게 사용할 수 있습니다.

완전 탐색을 통해 무조건 정답을 찾을 수 있지만 중복 계산되는 값도 있어 시간이 오래 걸릴 수 있습니다.

그렇기 때문에 문제의 데이터 범위를 보고 잘 사용해야 할 것 같습니다.

[참고 사이트]