브루트 포스

컴퓨터 과학 및 알고리즘 설계 영역에서 복잡한 문제에 대한 다양한 해결책이 있다. 여러가지 복잡하고 정교한 알고리즘이 있지만 더 직접적인 접근 방식을 취하는 알고리즘인 브루트 포스 알고리즘이 있다.

 

Brute Force Algorithm

Brute Force는 Brute(무식한)과 Force(힘)이 합쳐진 말로 힘으로 무식하게 해결하는 것을 말한다.

브루트 포스 알고리즘은 완전탐색 알고리즘이라고도 불리며, 모든 경우의 수를 다 확인하여 문제를 해결하는 알고리즘이다. 즉, 문제를 해결할 때까지 가능한 모든 입력 조합 또는 순열을 고려하여 간단하고 체계적인 접근 방식을 따른다. 단순성과 직관성이 특징으로 구현하기 쉽다.

 

장점

1. 단순성: 무차별 대입 알고리즘은 가능한 모든 솔루션을 체계적으로 반복하기 때문에 상대적으로 이해하고 구현하기 쉽습니다. 보다 최적화된 알고리즘이 개발되기 전에 문제 해결을 위한 출발점 역할을 합니다.

2. 정확성 보장: 무차별 대입 알고리즘은 가능한 모든 솔루션을 고려하기 때문에 충분한 시간과 리소스가 주어지면 최적의 솔루션을 찾는 것을 보장합니다. 그들은 잠재적 솔루션을 간과할 가능성을 제거합니다.

3. 작은 입력에 대한 적용 가능성: Brute force 알고리즘은 가능한 솔루션의 수가 관리 가능한 작은 입력 크기 문제에 적합합니다. 솔루션의 정확성을 프로토타이핑하고 확인하는 데 유용할 수 있습니다.

한계

입력 크기가 증가함에 따라 가능한 솔루션의 수가 기하급수적으로 증가한다. 결과적으로 대규모 문제에 대해 비실용적이거나 실행 불가능하다. 또한, 시간이 많이 소요된다.  메모리 및 처리 능력과 같은 필요한 컴퓨팅 리소스는 실제 한계를 초과할 수 있다. 예를 들어, 숫자로 구성된 비밀번호 4자리를 푸는 것은 간단하지만 9자 이상의 소문자, 숫자, 특수문자로 구성된 비밀먼호는 완전 탐색 알고리즘을 풀기에는 너무 시간 소요가 크다.

 

구현 방법

1. for / while loop

 

앞서 말한 비밀번호와 같이 0부터 9999까지의 숫자를 대입하면서 문제를 해결해 나가는 것 처럼 for문이나 while문을 이용해서 가능한 모든 경우의 수를 해결하면 된다.

 

2. 재귀 함수

 

모든 경우의 수를 해결할 때 가능한 모든 조합을 만들어야 하는 경우가 있다. 예를 들어, 숫자 카드 5장에서 2장을 써서 만들 수 있는 모든 경우의 수를 구한다고 했을 때, 완전 탐색 알고리즘을 사용하면 내가 이 카드를 사용할지 하지 않을지를 선택하여 재귀적으로 표현할 수 있다.