완전 탐색 (brute force) 알고리즘

개념 정리

브루트 포스 또는 완전 탐색이라고 불리우는 알고리즘이다.

brute "짐승, 짐승같은, 난폭한" + force "힘, 무력, 폭력"

굳이 해석하자면 짐승같은 힘, 난폭한 힘으로 해석될 수 있다.
또는 완전 탐색 알고리즘이라고 불리는데
완전 탐색이라는 말 그대로 모든 경우의 수를 탐색하는 알고리즘이라고 말할 수 있다.
따라서, 간단하게 말하면 모든 경우의 수를 직접 다 해보는 알고리즘이다.

특징

부르트 포스는 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식 으로 문제를 푸는 것 이다.
성공한다는 가정하에 항상 정확도 100%를 보장한다는 점에서 자원만 충분하면 가장 무서운 방법이다.
무식하게 보일 수 있지만 암호학에서는 가장 확실한 방법으로 통용되고 있다.
그래서 브루트 포스의 가장 큰 장점은 거의 완벽하게 병렬 작업이 가능하다는 점이다.

하지만, 시간적인 측면에서 비효율적인 알고리즘이라는 것.

예시

이해하기 가장 쉬운 예시가 하나 있다.
간단하고 쉬운 예시인데 1부터 100까지 더하는 것이다.
완전 탐색을 이용한다면 1부터 100까지 직접 더해서 값을 찾을 것이다.

1+1=2 , 2+2=4, 3+4=7, ··· , 4950+100=5050

이 예시를 C++ 코드로 작성해보았다.

#include <iostream>

using namespace std;

int main(){
	int sum = 0;
	
	for(int i=1; i<=100; i++){
		sum += i;
	}
	
	cout << sum << "\n";
}

반복문을 공부할 때 많이 사용했었던 코드였다.

그리고 또 하나의 예시로 암호를 예로 들 수 있다.
예를 들어 0~9까지의 숫자로 이루어진 4자리로 되어있는 암호가 있다고 하자.
그럼 암호에 들어갈 수 있는 숫자는 0000 부터 9999 까지가 된다.
브루트 포스 알고리즘을 이용하면 0000 부터 0001, 0002, 그리고 9999 까지 하나씩 다 대입해 볼 것이다.
9999까지의 경우의 수를 다 해본다면 암호를 풀 수 있겠지만 그만큼 시간이 많이 걸린 다는 것이다.

정리

브루트 포스는 완전 탐색 알고리즘이라고 불리고 있고 모든 경우의 수를 대입해 결과를 찾는 알고리즘이라는 것이다.
쉽게 접할 수 있는 알고리즘이었고 이해하기 쉬운 알고리즘이라고 생각한다.
정리해보면,

1) 완전탐색(브루트 포스) 알고리즘은 모든 경우를 탐색하는 알고리즘이다.
2) 완전탐색(브루트 포스) 알고리즘은 경우의 수에 따라 시간이 증가하기 때문에 시간적인 측면에서 비효율적이다.
3) 완전탐색(브루트 포스) 알고리즘은 만들기 쉽다.

처음에는 브루트 포스가 뭘까? 하면서 어려운 알고리즘인가? 생각했었는데 결국 노가다
생각보다 내가 공부하면서 봐왔던 코드나 예시들이 브루트 포스를 사용한 것이라는 것을 알았다.

시간상 비효율적이라고 해서 완전 탐색 알고리즘이 안 좋다는 것은 아니라고 생각한다.
복잡한 방법으로 푸는 것보다는 때로는 단순하게 푸는 것도 하나의 방법이다.

여러 검색을 통해 브루트 포스가 무엇인지 찾아보았는데
여러 사이트나 블로그를 보면서 '아, 이런 알고리즘이었구나.', '내가 했던 방법이 브루트포스였구나.'
하는 생각이 많이 들었다. 그만큼 우리가 쉽게 접할 수 있는 알고리즘이었고
브루트 포스 알고리즘 문제를 풀다보면 자연스럽게 익숙해질 것이라고 생각한다.

참고사이트

https://namu.wiki/w/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4

https://steemit.com/kr-dev/@gyeryak/easyalgo-2-bruteforce