[Brute Force]란 무엇인가?

오늘 아래의 문제를 풀기 위해 브루트 포스 알고리즘 방법을 사용했다.
브루트 포스로 문제를 풀었으니, 본 글은 브루트 포스를 정리하고자 한다.

https://haksae.tistory.com/187?category=948102 

[백준] 1436번 영화감독 숌

 

1. Brute Force란?

Brute : 무식한, 짐승, 동물
Force : 힘

• 이름에서 느껴지듯이, 매우 단순 무식한 알고리즘 방법으로, 완전 탐색 알고리즘이다.
• 즉 문제를 해결하기 위해서, 가능한 모든 경우의 수를 탐색하면서 요구 조건에 충족하는 결과를 가져오는 방법이다.

2. Brute Force의 장단점

• 장점
  • 모든 경우의 수를 탐색하기 때문에, 예외 없이 100%의 확률로 정답만을 출력한다.
  • 구현하기 쉽고, 다른 아록리즘을 생각하는 출발점이 된다.
• 단점
  • 모든 경우의 수를 탐색하기 떄문에, 경우의 수가 많아질 경우 시간복잡도가 엄청나게 늘어난다.
  • 즉 시간 면에서 매우 비효율적이다.

3. Brute Force의 종류

자료의 구조에 따라서 브루트 포스는 2종류로 나뉘게 된다.

- 선형구조 : 순차 탐색

- 비선형구조 : BFS, DFS

 

1) 순차 탐색

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

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

2) BFS, DFS

• 비선형 자료구조를 탐색하는 방법들이다.
• BFS는 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방식 (너비 우선 탐색)
• DBS는 루트 노드에서 가장 끝에 있는 막다른 노드까지 탐색을 해서 재귀적으로 탐색하면서 연결된 노드들을 탐색하는 방식 (깊이 우선 탐색)
• BFS, DFS는 모든 노드들을 탐색하기에 브루트 포스 방식의 알고리즘이다.