알고리즘 - 완전 탐색(Brute-Force Search) : 무차별 대입

브루트 포스 (BP) - 완전 탐색 알고리즘

브루트 포스는 Brute(짐승, 이성이 없는) + Force(힘) 짐승 같은 힘, 폭력이라는 뜻으로 무차별적이라는 뜻이다.

브루트 포스는 가장 단순하지만 가능한 모든 경우의 수를 탐색하며 정확도 100%의 중요한 알고리즘이며

'해가 하나 이상 존재 한다.'는 가정을 세우고 가능한 모든 경로를 탐색한다.

 

정확도가 100%라면 모든 문제를 브루트 포스를 사용하면 되지!

라고 생각했다면 반은 맞고 반은 틀린 문제이다. 물론 브루트 포스를 이용한다면 분명 답은 나올 것이다. 하지만 우리에게는 자원과 시간이 무한하지 않다는 것을 알아야한다. (핸드폰 비밀번호나 자물쇠 비밀번호와 같은 3, 4자리 비밀번호도 풀기 위해 많은 인내가 필요하다.)

 

브루트 포스를 이용하여 4자리 자물쇠 비밀번호를 알아내려고 하는 경우 1에서 9999까지 모든 경우의 수를 대입하려면

아래와 같은 코드를 이용하면 된다.

int sum = 0;
int pwd= ?;
 for(int i=1; i<=9999; i++) {
   if(sum == pwd){
   	 // 비밀번호 찾기 성공
   }
 }

하지만 자물쇠가 4자리 숫자가 아닌 잊어버린 나의 온라인 계정의 비밀번호를 찾으려 한다면

영문 소문자 * 대문자 * 숫자 (26*26*10) 그리고 비밀번호의 길이에 따라서 경우의 수는 기하급수적으로 늘어난다.

아래 표를 통하여 경우의 수를 확인해보자.

비밀번호 길이	경우의 수(영문+숫자조합)	경우의 수(특수문자포함)
6	61,474,519	156,238,908
7	491,796,152	1,473,109,704
8	3,381,098,545	11,969,016,345
9	20,286,591,270	85,113,005,120
10	107,518,933,731	536,211,932,256
11	508,271,323,092	3,022,285,436,352
12	2,160,153,123,141	15,363,284,301,456
13	8,308,281,242,850	70,907,466,006,720
14	29,078,984,349,975	298,824,321,028,320
15	93,052,749,919,920	1,155,454,041,309,500
16	273,342,452,889,765	4,116,305,022,165,110

10자리의 비밀번호를 찾는데에도 약 1천억 번의 대입을 해야만 비밀번호를 찾을 수 있다는 결론이 나오게 된다.

 

브루트 포스는 정확도 100%를 자랑하며 개발에서도 많이 쓰이는 알고리즘이지만

특별한 다른 방법이 없을 경우 사용하도록 해야한다.

---

브루트 포스의 종류

선형 구조 - 순차 탐색

선형구조인 순차탐색은 간단하게 문제를 해결할 수 있다.

문제 해결 방법

1. 주어진 문제의 자료를 선형 구조로 변경한다.
2. 선형 구조로 된 자료들을 탐색한다.
3. 탐색된 해를 출력형식에 맞도록 출력한다.

 

비선형 구조 : 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

비선형 구조인 너비 우선 탐색과 깊이 우선 탐색은 각 포스팅에서 다뤄보도록 하자.

 

---

브루트 포스 문제 풀러 가기