6 브루트포스

이전 포스트

경우의 수 덧셈규칙

http://ingyeoking13.tistory.com/162

경우의 수를 이용한 알고리즘

완전탐색 (Brute Force)

완전탐색은 기본적이면서, 중요한 알고리즘 패러다임인데요. 완전 탐색 알고리즘의 사용할 때, 문제를 해결하는 방식이 굉장히 직설적입니다. "완전" 이라는 단어도 그렇지만, 해당 문제의 조건을 보면 알 수 있습니다 ㅇㅅㅇ..

완전탐색 알고리즘은 그다지 좋은 알고리즘이 아닙니다. 왜냐하면 시간 복잡도가 지수 시간exponential time이기 때문이죠. 그래서 완전탐색을 사용한다는건 연산 장치의 리소스를 별로 신경쓰면서 문제를 해결하는 쪽은 아니라는 거죠.

일반적인 완전탐색 예로는, 모든 가능한 정답들을 검사해서 진짜 정답을 찾는겁니다. 제일 그럴듯한 정답을 위해서요. 그래서 일반적으로 완전탐색은, 문제의 어떤 특별한 구조를 이해하는 식의 노력이나 기발한 아이디어를 이용해서 정답을 찾는게 아니라는거죠.

여러분은 이미 완전탐색을 해보았을겁니다. 이미 나도 모르게 해봤다니, 알고리즘 한개 공짜로 먹었네 개꿀 ㅋㅋ 신이 나지 않나요?

않음 말구...

사실 주어진 배열에서 가장 큰 값을 찾는 것이 가장 간단한 완전탐색이라고 할 수 있습니다. 왜냐하면 sequence 내의 모든 수를 비교하면서 가장 큰 값을 찾기 때문이죠.

배열내 가장 큰 값을 찾는 알고리즘  <-- 기억안나면 클릭

버블, 삽입, 선택정렬 또한 완전탐색 알고리즘이라고 할 수 있습니다. 확실히 퀵 정렬 보다 덜 효율적입니다.

완전탐색 해킹?

알파벳 {'a','b','c','d','e','f'}가 있을 때  4 자로 이루어진 비밀번호의 경우의 수는 몇일까요? 6^4 입니다.

기억이 안난다면 여길 클릭

어떤 동작이 2개의 sub동작으로 이루어질 때, sub1 동작의 경우의수 * sub2 동작의 경우의수가 동작의 전체 경우의수가 됩니다.  그래요. 무슨말이죠? 제가 말을 이상하게하네요 

어쩃든 경우의 수를 곱하면된다 그겁니다. 그리고 이런 동작원리가 중첩 for문이 잘하는 역할이기도 합니다.

코드보기

https://github.com/ingyeoking13/algorithm/blob/master/tistory/ch6/brute.c

좀 더 그럴듯한 완전탐색을 이용한 비밀번호뚫기를 만들어보았습니다. 

코드보기

https://github.com/ingyeoking13/algorithm/blob/master/tistory/ch6/brute2.c

33자에 6자리라,  33^6, 1291467969 경우의 수이네요. 연산속도가 매우 느릴겁니다. 연산수 1억당 1초라고하면 12초정도 걸리겠습니다. 터미널에 출력하는 것말고 출력결과를 파일로 떨어뜨리면 체감속도가 더 빠를겁니다.

브루트포스는 반드시 중첩 for문으로 푸는게 아니지만 해당 문제가 요구하는 것이 꼭 중첩 for문 같은 명제들로 이루어져있습니다. 모든 경우의 수를 다 해본다는거죠! 브루트 포스 문제는 연산수가 n*n*n .....이런 n의 몇 승 형식, a*b*c... 라는 개별적인 사건 경우의수의 곱 이라거나 n*(n-1) *(n-2)* .. 이런 팩토리얼형식입니다.

브루트포스를 이용해서 풀 수 있는 문제들

백준 온라인저지 브루트포스 문제집

이 문제 또한 brute force로 풀수있습니다.  (다이내믹 프로그래밍으로 분류되어있지만 ㅠ.ㅠ...)

https://www.acmicpc.net/problem/9095

소스보기 (  변태적인 for문을 볼 수 있습니다. 예, 전 변태입니다. 연산수는 3^10승입니다.)

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/p9095_brute.c

브루트포스의 개념을 이용한 것이 dp 이고, dp 또한 모든 경우의 수를 다 해봅니다. 그러니까 표현하자면 "조심스럽게 사용하는 완전탐색에 가깝다"라고 불리기도 합니다. 그러나, 좀 더 똑똑한 방식으로 하는 것이죠. 브루트 포스는 지수시간 복잡도인 반면에, dp는 다항시간안에 연산이 가능합니다. 그리고 dp는 매우 다양한 난이도인 초, 중, 고급 알고리즘 문제들로 만날 수 있습니다.

우선 dp설명은 여기까지하고, 다음 컨테츠인 순열조합으로 넘어가보죠

순열과조합은 factorial의 연산수가 나옵니다. 

순열과 조합은,, 근데 포스트 길이가 너무기네 다음 포스트로 넘어갈게요

다음 컨텐츠

순열과조합

http://ingyeoking13.tistory.com/164