[Algorithm] Brute Force (브루트 포스)

브루트 포스

브루트 포스란?

brute 동물
force 힘

직관적으로 무식하게 힘을 쓰는 알고리즘이다.
처음부터 끝까지 계산을 다 해나가면서 해를 찾는 방식이다.
즉, 문제를 해결하기 위해서 가능한 모든 경우에 대해 모두 직접 해보는 방식이다.

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

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

브루트 포스 종류

자료의 구조에 따라 2가지로 나뉘게 되는데
선형 구조 - 순차탐색
비선형 구조 - BFS, DFS

순차 탐색

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

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

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);
}