brute-force

모든 경우의 수를 다 해보는 것.

• 예를 들어, 비밀번호가 4가지이고, 숫자로만 이루어져 있으면

• 0000~9999까지 전부다 입력해보면 됨

• 경우의 수는 10,000가지.

다른 예제를 보자.

• 예를 들어, 비밀번호가 12자리이고, 숫자로만 이루어져 있으면

• 00000000000~ 999999999999

• 1조개.

실제로 구현을 하게되면,

• 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간제한을 넘지 않아야 한다.

  • 1초 : 1~10억번 연산

실제 브루트 포스 할 수 있는거는 백만에서 천만정도

브루트포스로 문제 풀려면

• 문제의 가능한 경우의 수를 계산. : 가지수

  -> 10000가지

• 가능한 모든 방법을 다 만들어봄 : 코딩

  -> 0000~9999까지 포문 돌리기

• 각각의 방법을 이용해 답을 구하기.

1. 문제의 가능한 경우의 수를 계산해본다.

   • 직접 계산을 통해 구하기. 손으로 계산 가능.

2. 가능한 모든 방법 다 만들기.

   • 하나도 빠짐 없이 만들기

   • 대표적으로 그냥 다 해보는 방법, for문 / 순열 / 재귀호출 / 비트마스크 사용

     • 순서가 중요할 때 순열 사용.

3. 각 방법을 이용해 답을 구한다.

   • 문제에 나온 대로 답을 계산

브루트 포스 시간 복잡도는 O(경우의 수 방법 1개를 시도해보는데 걸리는 시간 복잡도) 즉, 2번에 걸리는 시간 3번에 걸리는 시간.