완전 탐색 알고리즘(Brute-Force Algorithm)

• Brute Force Algorithm 은 무차별 대입 방법을 나타내는 알고리즘이다. 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법이라 할 수 있다. Brute Force는 최적의 솔루션이 아니라는 것을 의미하기도 하는데, 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법이기 때문다.

• Brute Force Algorithm 은 크게 두 가지 경우에 사용된다.

  • 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
  • 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

이처럼 Brute Force Algorithm은 문제에 더 적절한 해결 방법을 찾기 전에 시도하는 방법이지만, 데이터의 범위가 커질수록 상당히 비효율적이다.

한계

Brute Force Algorithm 은 문제의 복잡도에 매우 민감한 단점을 가지고 있다. 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘이다. 여기서 자원은 시간이 될 수도 있고 컴퓨팅 자원이 될 수도 있다.

용례

• 순차 검색 알고리즘 (Sequential Search)

배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색한다.

public boolean SequentialSearch2(int[] arr, int K) {
 // 검색 키 K를 사용하여 순차 검색을 구현
 // 입력: n개의 요소를 갖는 배열 A와 검색 키 K
 // 결과를 저장할 boolean result선언, 초기값은 false
 // 출력: K값과 같은 요소 인덱스 또는 요소가 없을 때 false

 int n = arr.length;    // 현재의 배열 개수를 n에 할당
 boolean result = false;
  for(int i = 0; i < n; i++) {
    if(arr[i] == K) {
      result = true;
    }
  }
  return result;
}
       
//배열을 순회하는 도중에, 해당하는 값이 발견되더라도 배열을 모두 순회한 이후에 결과값을 리턴

• 문열 매칭 알고리즘 (Brute-Force String Matching)

길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색한다.

public boolean BruteForceStringMatch(int[] arr, int[] patternArr) {
    // Brute Force 문자열 매칭을 구현한다.
    // 입력: n개의 문자 텍스트를 나타내는 배열 T, m개의 문자 패턴을 나타내는 배열P
    // 출력: 일치하는 문자열이 있으면 첫번째 인덱스를 반환한다. 검색에 실패한 경우 -1을 반환한다.
    int n = arr.length;
    int m = patternArr.length;
    for (int i = 0; i < n - m; i++) {
      // 전체 요소개수에서 패턴개수를 뺀 만큼만 반복한다. 그 수가 마지막 비교요소이기 때문이다.
      // i 반복문은 패턴과 비교의 위치를 잡는 반복문이다.
      int j = 0;
      // j는 전체와 패턴의 요소 하나하나를 비교하는 반복문이다.
      while (j < m && patternArr[j] == arr[i + j]) {
        // j가 패턴의 개수보다 커지면 안되기때문에 개수만큼만 반복한다.
        // 패턴에서는 j인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단한다.
        // 같을때 j에 +1 한다.
        j = j + 1;
      }
      if (j == m) {
        // j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분이 존재한다는 의미.
        // 이 때의 비교했던 위치를 반환.
        return true;
      }
   }
   return false;
 }

• 선택 정렬 알고리즘 (Selection Sort)

전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘이다.

public int[] SelectionSort(int[] arr) {
    // 주어진 배열을 Selection Sort로 오름차순 정렬한다.
    // 입력: 정렬 가능한 요소의 배열 A
    // 출력: 오름차순으로 정렬된 배열
    for (int i = 0; i < arr.length - 1; i++) {
      // 배열의 0번째 인덱스부터 마지막인덱스까지 반복한다.
      // 현재 값 위치에 가장 작은 값을 넣을 것이다.
      int min = i;
      // 현재 인덱스를 최소값의 인덱스를 나타내는 변수에 할당한다.
      for (int j = i + 1; j < arr.length; j++) {
        // 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소과 비교하는 반복문을 구성
        if (arr[j] < arr[min]) {
          // j인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면
          min = j;
          // j 인덱스를 최소를 나타내는 인덱스로 할당한다.
        }
      }
      // 반복문이 끝났을 때(모든 비교가 끝났을때)
      // min에는 최소값의 인덱스가 들어있다.
      // i값과 최소값을 바꿔서 할당한다.
      int temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  // 모든 반복문이 끝나면 정렬된 배열을 반환한다.
  return arr;
}

추가 공부할 키워드

• Brute Force vs Dynamic Programing
• Closet-Pair Problems by Brute Force
• Convex-Hull Problems by Brute Force