Week 13 ::Brute Force Algorithm

Brute: 짐승, 저돌적인, 무식한 Force: 힘

Brute Force: 무식하게 모든 경우의 수에 대한 탐색을 진행하는 알고리즘

 

ex) 0000 ~ 9999 사이에 비밀번호가 있을경우 10^4번의 경우의 수에 해당하는 값들을 모두 입력 비교

 

-완벽하게 병렬작업이 가능한 알고리즘이다.

 쉽게 말해 모든 경우를 따지기 때문에 '분업'해서 탐색을 진행할 수 있다.

 

 

-브루트 포스 알고리즘은 조건의 영향을 아주 많이 받는 알고리즘이다.

- 그래서, 문제의 조건이 지원되는자원의 범위 속에 있다면 정확도를 위해서 좋을 수 있으나 그렇지 못한 여건에서

  '다이나믹 프로그래밍'이나 '인공지능'등의 다른 방법으로 강구되어야한다.

- 하지만, 여전히 암호학에서는 정확도측면에서 많이 고려되어 사용되어지는 알고리즘 이기도 하다 (Brute Force Attack)

 

 

Solution:

-유추되는 모든 경우의 수를 전부 확인하도록 한다.

- 주로 사용되는 방식은

1) for - loop

2) 순열(permutation) 사용 ★ next_permutation / previous_permutation

3) 재귀(recursion) 사용

4) 비트마스크 (bit-masking, 각각의 bit를 true를 true/false 마킹 용도) 사용 ★ -> 공간적인 최적화 사용 가능

 

 

순열의 경우

10972번: 다음 순열

// BRTFRC_10972.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector <int> d;
int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int c; cin >> c;
		d.push_back(c);
	}

	if (next_permutation(d.begin(), d.end())) {
		for (int i : d) {
			cout << i << ' ';
		}
	}
	else cout << -1;
	
}

 

next_permutation - C++ Reference