[Algorithm] 부르트 포스 알고리즘

  부르트 포스  (Brute Force)

- 모든 경우의 수를 파악해야할 때 사용한다. [완전 탐색]

- 경우의 수를 만들기 위한 방법을 작성해야한다. (순열, 재귀, 비트마스크 등)

---

  알고리즘  

1. 부르트 포스 문제가 맞는지 확인한다.
    a. 문제가 모든 경우의 수를 파악해야하는 경우
    b. 입력되는 데이터의 범위가 작고, 시간 제한이 꽤 긴 편이다.
        - [1초 당 연산 횟수] 
           O(N) = 1억
           O(NlogN) = 500만  
           O(N^2) = 1만
           O(N!) = 11

2. 어떤식으로 경우의 수를 만들지 결정하기 (순열, 재귀, 비트마스크 등)
    a. 단순한 문제 => 반복문 사용
    b. 사전성(순서) 확인 => 순열 사용
    c. 가지치기를 하는 경우 => 재귀
        - 중간에 답이 아닌 것이 확실해지는 것이 한 무더기 생기는 경우라고 생각하자.
        ex) 탐색 중 정답에는 1이 들어가지 않는 것이 확실해진다 -> 1이 들어가는 모든 경우는 제외하고 탐색

참고 영상 

---

  Key point!  

📍부르트 포스 만으로 풀 수 있는 문제는 거의 나오지 않지만, 이가 기반이 되는 문제가 출제될 확률이 높다.

📍경우의 수를 만들 수 있는 방법 선택이 중요하다. 문제를 많이 풀어 감을 익혀야한다.

---

  관련 문제