알고리즘 - 브루트포스(Brute-Force)

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

1. 브루트포스(Brute-Force)란?

Brute : 짐승같은

Force : 힘

짐승같은 즉, 무식한 방법으로 확인한다는 뜻이다.

완전 탐색 알고리즘으로 가능한 모든 경우의 수를 전 부 다 탐색하면서 조건에 충족되는 값을 도출해내는 알고리즘이다. 

 

예를 들어 1부터 100사이의 짝수의 갯수를 구하는 문제라고 가정해보자.

하나의 변수를 1부터 시작하여 해당 숫자가 짝수인지 파악하고, 짝수라면 카운트를 올려준다. 그 후 숫자에 1을 더하고 위 과정을 반복한다. 그러다가 숫자가 101이 되면 종료하는 방식이다.

 

간단한 코드로 나타내면

 

for(i = 1; i < 101; i++){

    if(i % 2 == 0) coumt++;

}

 

이런 방식이다.

 

2. 브루트포스 알고리즘의 장단점?

장점

1. 알고리즘을 설계하고 구현하기 정말 쉽다.

: 복잡한 알고리즘이라기보단 하나씩 전부 확인하는 알고리즘이기때문에 만들기가 쉽다.

2. 다른 알고리즘을 생각하는데 시작점이 된다.
: 브루트포스 알고리즘은 하나씩 전부 확인하는 알고리즘이다. 이런 과정을 거치며 예외를 하나씩 하나씩 넣게되고, 더 개선된 알고리즘을 본인의 힘으로 찾아가게 만들어줄 수 있다.

 

단점

1. 실행시간이 매우 느리다.

: 단순히 생각해봐도 느릴수 밖에 없다. 모든 경우의 수를 하나씩 하나씩 전부 확인하게 되는데 경우의 수가 늘어나면 늘어날수록 소요되는 시간도 기하급수적으로 늘어난다. 예를들어 위의 예시 숫자가 1부터 10000000이라면 10000000번 연산을 해야한다. 

2. 메모리 효율면에서 매우 비효율적이다.

: 위의 이유와 동일하다. 

 

3. 어떻게 사용하나?

브루트포스는 크게 선형구조와 비선형구조로 나누어서 볼 수 있다.

선형구조 : 순차탐색

비선형 구조 : 백트래킹, DFS, BFS

 

순차탐색이란 위의 예시처럼 순서대로 하나씩 다 확인하는 방법이다

 

DFS와 BFS는 이전에 내가 적어둔 알고리즘이 있다. 한번 읽어보는걸 추천한다. 

https://naemamdaelo.tistory.com/37

알고리즘 - 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

4. Example

https://naemamdaelo.tistory.com/23

[Java] 백준 1436번 : 영화감독 숌

 

-꿑-