Brute Force & Back Tracking

1. brute force란?

Brute Force는 완전 탐색 알고리즘이라고 할 수 있다.
즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만 가지고 온다.
이 알고리즘의 장점은 예외 없이 100%의 확률로 정답만을 출력 할 수 있다.

1-1. 구조에 따른 brute force 종류

• 일반적인 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색 할 수 있는 방법을 필요로 한다.
• brute force에 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
• 선형 구조를 모두 탐색하는 방법은 가장 간단한 순차 탐색이 있다.
• 비선형 구조를 모두 탐색하는 방법은 BFS, DFS가 있다.

1-2. 정리

• brute force 알고리즘은 모든 경우를 직접 하는 알고리즘이다.
• brute force 알고리즘은 시간 면에서 매우 비효율적이다.
• 만들기 쉽고, 다른 알고리즘을 생각하는 출발점이 된다.

2. Back Tracking란?

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

dfs와 비교 해보면, dfs는 가능한 모든 경로를 탐색한다. 따라서, 불 필요할 것 같은 경로를 사전에 차단하거나 하는 등의 로직이 없으므로 경우의 수를 줄이지 못한다.

백트래킹은 해를 찾아가는 가면서, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다.

2-1. 정리

• back tracking은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.
• 즉, 답이 될 수 있는지 판단하고 그렇지 않으면 끝까지 탐색하지 않고 올바른 쪽으로 간다.