[알고리즘] 무차별 대입 (Brute Force)

Brute Force

개념

• 문제를 해결하기 위해 가능한 모든 경우의 수를 모두 시도하는 방식.

• 단순하고 구현이 쉽지만, 경우의 수가 많아질수록 시간복잡도가 커질 수 있다.

특징

• 가능한 모든 경우의 수를 순차적으로 탐색하므로 해답을 반드시 찾을 수 있다.

• 최적화된 알고리즘에 비해 효율이 낮고 시간복잡도가 크다.

• 효율을 개선하기 위해 백트래킹이나 DP 같은 최적화 알고리즘을 사용한다.

절차

1. 해답이 될 수 있는 모든 경우의 수를 나열

2. 각 경우를 하나씩 검사하여 조건에 만족하는지 확인

3. 조건에 만족하는 답을 찾으면 반환하고, 아니면 계속 시도

4. 모든 경우를 다 시도해도 찾지 못하면 없다고 결론

예시

비밀번호 추측 문제

for(int i = 0; i <= 1000; ++i){
		if(i == password){
				cout << "correct";
				break;
		}
}