[Algorithm] Brute Force(부르트 포스)

부르트 포스

부르트 포스란?
brute 동물
force 힘
직관적으로 무식하게 힘을 쓰는 알고리즘이다. 처음부터 끝까지 계산을 다 해나가면서 해를 찾는 방식이다.
문제를 해결하기 위해서, 가능한 모든 경우에 대해 모두 직접 해보는 방법입니다.

ex) 1부터 100까지의 합을 구하라
0 + 1 = 1
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
.
.
.
4950 + 100 = 5050

브루트 포스의 가장 흔한 문제점은 숫자가 커지면 커질수록 시간복잡도가 엄청나게 늘어나는 것입니다.

브루트 포스 종류

자료의 구조에 따라서 브루트포스는 2종류로 나뉘게 되는데,
선형구조 - 순차탐색
비선형구조 - BFS, DFS

순차 탐색

순차 탐색을 하는 방식은 정형화 되어있습니다.

1. 문제에서 주어진 자료를 선형 구조로 바꾼다.
2. 구조화된 자료들을 구조에 맞는 방법으로 해를 구할 때까지 탐색한다.
3. 탐색한 해를 주어진 문제의 출력 형식에 맞게 정리합니다.

브루트 포스 문제
ex) 문제 및 해결

BFS

선형 탐색을 이용하여 탐색을 할 수 없는 구조들이 있습니다. 대표적으로 그래프 자료구조가 있습니다. 그래프 형태의 자료구조들은 탐색을 할 때, 선형탐색이 불가능하기 때문에 비선형 구조 탐색법을 사용해야 합니다. 그 중에 하나다 너비 우선 탐색(BFS)입니다.

너비우선 탐색이란?

루트노드에서 시작해서 인접한 노드를 먼저 탐색하는 기법입니다. 인접한 노드들을 각각 큐에 넣어 놓고 큐에서 하나씩 꺼내서 큐에서 나온 노드와 연결된 노드들을 순차적으로 먼저 탐색하고 또 인접한 노드중에서 방문되지 않은 노드들을 지속적으로 탐색한다.

코드

void bfs_search(GraphType *g, int v)
{
	QueueList q;
	int w;
	queue_init(&q);

	visited[v] = 1;
	printf("%d ->", v);
	enqueue(&q, v);
	while(!queue_empty(&q)){
		v = dequeue(&q);
		for(w = 0;w < g -> n;w++)
			if(g -> adj_mat[v][w] && !visited[w]){
				visited[w] = 1;
				printf("%d -> ", w);
				enqueue(&q, w);
		}
	}
}

DFS

깊이 우선 탐색

DFS는 이름과 같이 루트에서 가장 끝에 있는 막다른 노드까지 탐색을 해서 재귀적으로 함수가 탐색을 갔다가 빠져나오면서 연결된 노드들을 탐색하는 방식입니다.

코드

void dfs_search(GraphType *g, int v)
{
	int w;
	visited[v] = 1;
	printf("%d ->", v);
	for(w = 0;w < g -> n;w++)
		if(g -> adj_mat[v][w] && !visited[w])
			dfs_search(g, w);
}

참고