[알고리즘 - 기초] 완전 탐색, 브루트 포스 (Brute Force)

완전 탐색, 브루트 포스란 무엇인가?

---

브루트 포스를 사전적 의미로 찾아본다면 아래와 같다.

 

브루트(Brute) : 무식한     +     포스(Force) : 힘

 

즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다.

전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.

 

브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.

 

 

브루트 포스의 장점

---

• 알고리즘을 설계하고 구현하기 매우 쉽다.
• 복잡한 알고리즘 없이 빠르게 구현할 수 있다.

 

 

브루트 포스의 단점

---

• 알고리즘의 실행 시간이 매우 오래 걸린다.
• 메모리 효율면에서 매우 비효율적이다.

 

 

브루트 포스의 종류

---

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

 

• 선형 구조 : 순차 탐색
• 비선형 구조 : 백트래킹, DFS, BFS

백트래킹과 DFS, BFS에 대해서는 나중에 그래프 탐색 알고리즘을 다룰 때 자세하게 설명하는 것으로 하고 여기서는 순차 탐색에 대해 다뤄보도록 하겠다.

 

 

브루트 포스 예시

---

만약 10자리 비밀번호 자물쇠가 있다고 가정해보자.

이 자물쇠를 풀기 위해서 브루트 포스 방식을 적용한다면  0000000000에서 9999999999까지 모든 수를 대입해서 풀어야 할 것이다.

아무리 요즘 컴퓨터의 성능이 좋다 하더라도 짧은 시간 안에 이것을 해결하기는 무리가 있다.

 

또 다른 브루트 포스 예시를 들어보자.

1부터 100억까지의 합을 브루트 포스로 구한다고 하면 반복문으로 1부터 100억까지 증가시키면서 total 변수에 누적시켜야 할 것이다.

등차수열의 합 공식을 사용한다면 쉽게 해결할 수 있는 문제이기 때문에 이것을 브루트 포스로 해결한다면 시간적, 메모리적으로 매우 비효율적인 해결 방법이 된다.

 

 

예제로 알아보는 브루트 포스

---

브루트 포스 문제를 해결해보기 위해 아래 블랙잭 문제를 풀어보자.

 

2798번: 블랙잭

 

[Solution]

[BOJ] 2798번: 블랙잭 (C, C++, Java, Python3)