완전 탐색 기본 개념 (브루트 포스 알고리즘)

yeong-min·2022년 6월 26일

알고리즘

영어로 Brute-Force 단순직역하면 무식하게 풀기이다

종류

순열

백트래킹

BFS

4자리 암호를 입력할 때
0000 ~ 9999까지
모두 대입하여 넣는 것과

패턴을 푸는 가짓수 모두 브루트 포스 알고리즘이다.

시간 계산

완전 탐색 은 무식한 방법으로 사람은 편하지만 기계는 힘들다!
-> 적용하기 전에 시간은 우리가 계산해주어야 한다!

보통 1억번의 연산 = 1초
O(N) : 1억
O(NlogN) : 5백만
O(N^2): 1만
O(N!): 11

2. 백트래킹

정의

해를 찾는 도중 해가 아니여서 막히면, 되돌아가서 다시 해를 찾아가는 기법

영어 그대로 막히면 돌아가서(back) 다시 추적해라(track) back+tracking

why 브루트포스(brute force)를 쓰지 않고 백트래킹을 하는 이유는?
백트래킹(Backtracking)은 코딩에서는 반복문의 횟수를 줄일 수 있으므로 효율적이다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

가지치기란? 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다

시간 복잡도

중복 허용할 때 : N^N (N = 10까지 가능)
중복 허용 안 할 때 : N! (N = 8까지 가능)
위처럼 시간 복잡도가 높기 때문에 N의 최댓값이 적을때 백트래킹으로 푸는 문제일 가능성이 높다.

소스 코드

#include <iostream>
using namespace std;

int N, M;
int arr[9];
bool visited[9];

void dfs(int k) {
	if (k == M) {
		for (int i = 0; i < M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
        return;
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				arr[k] = i;
				dfs(k + 1);
				visited[i] = false;
			}
		}
	}
}

int main() {
	cin >> N >> M;
	dfs(0);


	return 0;
}