[알고리즘] 완전 탐색 • 브루트 포스 (Brute Force)

이전 글 : )

[알고리즘] 자료구조 - 재귀 함수 ( Recursive Function ) ( + 팩토리얼과 피보나치수열)

 

 브루트 포스  brute force 

브루트 포스는 완전 탐색 알고리즘으로 가능한 모든 경우의 수를 모두 탐색하고 조건에 맞는 결과만을 가져옵니다.

즉 모든 경우의 수를 탐색함으로 이론상으로 항상 정확도가 100%를 보장합니다.

이러한 특징을 이용한 대표적인 암호 해독법으로 무차별 대입 공격(Brute Force attack)이 있습니다.

 

 

 자료구조에 따른 브루트포스 알고리즘 종류 

 

브루트 포스는 일반적으로 자료 탐색 알고리즘으로 쓰이기에 자료구조에 따라 종류가 나뉩니다.

선형 구조는 브루트 포스를 순차 탐색 방법으로 탐색하며,

비선형 구조는 BFS(넓이 우선 탐색)와 DFS(깊이 우선 탐색) 방법으로 탐색을 합니다.

BFS, DFS 다음에,,,

 

 

 순차 탐색  sequential search 

 

순차 탐색은 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘입니다. 브루트 포스의 의미와 같음을 알 수 있습니다.

https://thecleverprogrammer.com/2020/09/10/linear-search-algorithm-with-python/

1. 탐색 대상 자료를 선형 구조로 구조화합니다.

2. 구조화된 자료를 구조에 맞는 방법으로 해를 구할 때까지 탐색합니다.

3. 탐색한 해를 주어진 문제의 출력 형식에 맞게 정리합니다.

 

 

 예제 

 

순차 탐색을 이용해 배열 내부에 특정 요소가 존재하는지 찾는 예제 코드입니다.

배열 'arr'에서 x변수에 저장된 '10'이 존재하는지 찾습니다.

'search'함수를 보면 배열과 배열의 길이, 찾을 요소를 매개변수로 받으며 내부의 for 반복문은 arr배열을 처음부터 순차적으로 순회하면 10을 찾습니다.

# 브루트포스_순차 탐색 방법 예제

def search(arr, n, x):
 
    for i in range(0, n):
        if (arr[i] == x):
            return i
    return -1
 
 
# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10
n = len(arr)
 
# Function call
result = search(arr, n, x)
if(result == -1):
    print("배열에서 요소를 찾을 수 없습니다.")
else:
    print(result, "번 index에 요소가 존재합니다.")

 

 

 마무리 

 

 브루트 포스는 "Brute (무식한) + Force (힘)"의 뜻을 가지며, 말 그대로 무식하게 처음부터 끝가지의 경우의 수를 대입 또는 탐색하는 방법입니다. 이러한 방법의 특성상 정답을 무조건 100% 찾을 수 있다는 장점이 있지만 모든 경우의 수를 순회한다는 점에서 자원이 문제이며 문제의 복잡도에 매우 민감하다는 치명적인 단점이 있다고 합니다.

 여담으로 최대 8자리인 비밀번호를 풀기 위해서는 영문 대소문자, 숫자를 충족하는 사전 파일을 면 그 텍스트 파일의 용량은 34^8 바이트이며, 이것을 GB로 환산해보면 대략 1663GB가 나온다고 하네요.

 

---

 

 

[알고리즘] 정렬 알고리즘 (Sorting Algorithm)