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

김수민·2023년 3월 31일
0

백엔드 부트캠프

목록 보기
37/52

Brtue Force Algorithm (BFA)

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(String [] arr, String[] 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].equals(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 활용 알고리즘
    - 버블 정렬 알고리즘 - Bubble Sort
    - Tree 자료 구조의 완전 탐색 알고리즘 - Exhasive Search (BFS, DFS)
    - 동적 프로그래밍 - DP(Dynamic Programing)

0개의 댓글