Brute-Force

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

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

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

Brute Force Algorithm은 문제에 더 적절한 해결 방법을 찾기 전에 시도하는 방법입니다. 그러나 데이터의 범위가 커질수록 상당히 비효율적이다. 프로젝트의 규모가 커진다면 더 효율적인 알고리즘을 사용 해야 한다.

Brute Force Algorithm의 한계

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

일반적으로 문제의 규모가 현재 자원으로 충분히 커버가 가능한 경우에 Brute Force Algorithm을 사용한다. 만약 이를 벗어난 경우는 정확도를 조금 희생하고 더 효율적인 알고리즘을 사용한다.

사용 예시

• 순차 검색 알고리즘 (Sequential Search)
  배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색한다.
  

• 문자열 매칭 알고리즘 (Brute-Force String Matching)
  길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색한다.

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

그 밖의 Brute Force 활용 알고리즘

• 버블 정렬 알고리즘 - Bubble Sort
• Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS)
• 동적 프로그래밍 - DP(Dynamic Programing)