[알고리즘] 브루트 포스 (완전 탐색)

이 글은 혼자 공부하면서 적어간 내용이기에 평어체로 작성되었고 틀린 내용이 있을 수 있습니다.
이 점 양해부탁드리며 틀린 내용 지적, 질문은 언제든 환영합니다!

브루트 포스 (brute force)

브루트 포스 알고리즘은 완전 탐색 알고리즘 중 하나이며 가능한 모든 부분을 탐색하여 결과를 찾아내는 기법이다.

brute : 1.짐승 2.신체적인 힘에만 의존하는 의 맥락으로 추측해볼 수 있듯이 브루트 포스 알고리즘은 그냥 무식하게 모든 경우의 수를 탐색하는데 중점을 두고 있다.

브루트 포스의 장점

• 알고리즘 구현에 있어 간단하다.
  - 다른 알고리즘에 비해 시간이나 공간 복잡도에 대해서 크게 생각할 필요 없이 모든 경우를 탐색한다는 것에 중점을 두고 설계하면 된다.
• 보다 정확한 결과를 도출해낸다.
  - 다른 탐색 알고리즘들은 최적화된 방식으로 탐색하지만 무식하게 모든 결과를 검사함으로써 느리지만 정확한 결과를 얻어낼 수 있다.

브루트 포스의 단점

• 시간 복잡도, 공간 복잡도 측면에서 비효율적이다.
  - 브루트 포스 알고리즘을 위한 탐색 문제가 아닌 경우 시간 초과, 메모리 초과가 되기 쉽다.

예시

백준 2798번 블랙잭은 숫자가 적힌 여러 카드와 값 하나가 입력으로 주어지고 이 입력받은 값을 넘지 않는 선에서 카드 3장의 합을 가장 크게 만들어내는 문제이다.

👉 카드 3장의 합이 될 수 있는 모든 경우의 수를 탐색하여 결과를 도출하면 된다. 브루트 포스 알고리즘을 사용하는 문제이기 때문에 다른 것은 생각할 필요없으므로 그냥 for문만으로 무식하게 탐색하면 되는 것이다.

#include<iostream>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	int sum, ans=0, card[n+1];
	for(int i=0; i<n; i++)
		cin >> card[i];
	for(int i=0; i<n-2; i++) {
		for(int j=i+1; j<n-1; j++) {
			for(int k=j+1; k<n; k++) {
				sum = card[i]+card[j]+card[k];
				if(sum<=m && m-sum<m-ans)
					ans=sum;
			}
		}
	}
	cout << ans;
}

참고 문헌

https://foreverhappiness.tistory.com/104