브루트 포스(Brute Force)

• 브루트 포스(Brute Force)는 모든 경우의 수를 한번 씩 다 시도 해보는 것이다.
  여기서 모든 경우의 수는 가능한 문제 방법을 의미하고
  이 경우의 수가 몇가지 나오는 것을 알아보는게 중요.

ex)
비밀번호가 4자리이고 숫자로만 이루어져있다면 0000부터 9999까지 다 입력해보면 된다.
경우의 수는 10,000가지 -> 10,000초(1가지에 1초일 때)

비밀번호가 12자리이고 숫자로만 이루어져있다면 000000000000부터 999999999999까지 다 입력해보면 된다.
경우의 수는 10^12가지 -> 10^12초(1가지에 1초일 때)

똑같은 문제인데 방법의 개수에 따라서 가능한 정도가 달라진다.
그러므로 브루트포스는 적은수에서만 사용가능하고 모든 문제를 풀수 있지 않다.

---

브루트포스의 3단계

브루트포스로 문제를 풀기 위해 다음 3가지 단계를 생각해볼 수 있다.

1. 문제의 가능한 경우의 수를 계산 (코드X, 사람이 직접 계산)

2. 가능한 모든 방법을 다 만들어본다.

1) 다 해보는 방법 (주로 반복문을 의미, for문 사용)
2) 순열 사용  
3) ⭐재귀 호출 사용⭐ (순열,비트마스크를 몰라도 대신 사용할 수도 있다.)
4) 비트마스크 사용

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

이때 답의 조건이 최소, 최대, 경우의 수(가능여부에 따른 수)로 나뉠 수 있다.

⏳ 브루트포스의 시간복잡도 : O(방법의 개수 x 시도하는 복잡도)

---

경우의 수

브루트포스에서는 경우의 수를 구하는 것이 가장 중요하므로 다양한 경우의 수의 예시를 봐보자.

⭐1. Factorial⭐

• N명의 사람이 한줄로 서는 경우의 수 : ⭐ N! ⭐
  -> N x (N-1) X (N-2) X...X 1 = N!

Factorial의 제한 : N≤10

10! = 3,628,800(1억을 넘기면 안됨)
또 시도하는 복잡도까지 곱하면 1억을 넘기 때문

2-1. 구성만 의미있고 순서는 의미 없을 때 : nCr

• N명의 사람 중에서 대표 2 명을 뽑는 경우의 수 : N(N-1)/2x1 = O(N²)
• N명의 사람 중에서 대표 3 명을 뽑는 경우의 수 : N(N-1)(N-2)/3x2x1 = O(N³)

2-2. 같은 구성이여도 순서가 중요 : N!

• N명의 사람 중에서 반장 1명, 부반장 1명 : N x (N-1) = O(N²)

3. ⭐Xⁿ⭐

• N명의 사람이 있을 때, 각 사람이 영화를 볼지, 보지 않을지 결정. 가능한 조합의 수 : 2ⁿ= O(2ⁿ)
• N명의 사람이 있을 때, 각 사람이 세가지 영화 중 어떤걸 볼지 결정할 조합의 수 : 3ⁿ= O(3ⁿ)

Xⁿ의 제한 : N≤20
2^20 = 1,048,576