브루트 포스
브루트 포스(Brute Force) 기본
모든 경우의 수를 다 해보는 것.
- 깊게 생각할 필요 없음. 단순함.
- 예를 들어 비밀번호가 4자리이고 숫자로만 이루어져 있다면 0000부터 9999까지 다 입력해보면 된다. 이럴 경우 경우의 수가 10,000가지이다.
- 입력 크기가 굉장히 중요하다.
- 모든 문제에 적용할 수는 없다.
어떻게 사용할까
- 총 몇 개인가?
- 크지 않은가? (1억개 이하인가?)
- 그렇다면 모든 방법을 만들자
- 값을 구해라
브루트 포스(Brute Force) 순열
- 순서가 중요
- 사전순으로 나열하기
- 다음 순열 찾기: 순서를 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법
브루트 포스(Brute Force) 비트마스크
비트(bit) 연산을 사용해서 부분 집합을 표현하는 것. 정수로 집합을 나타내는 것.
- 연산자 우선순위 신경쓰기
브루트 포스(Brute Force) 재귀
순열과 비트마스트를 모르더라도 재귀함수로 대체할 수 있음
대부분의 브루투포스 재귀는 n개가 있고, 앞에서부터 차례대로 정렬하면서.. 이런 스타일임.
브루트 포스(Brute Force) 백트래킹
브루투 포스처럼 탐색을 계속 하다가, 탐색을 중간에 더 이어나가지 않는 코드를 작성하면 백트래킹이라고 한다.
- 정확한 시간 복잡도를 모른다. 왜냐면 중간에 잘리기 때문.