Brute-Force 알고리즘(완전탐색)

1. Brute-Force 알고리즘이란? 

- 브루트 포스 알고리즘은 이름의 뜻 처럼, 무식하게 푸는 방법이다.

- 브루트 포스 알고리즘은 모든 경우의 수를 파악하여 문제를 푸는 방법이다. 이를 완전탐색이라고 부르기도 한다.  

- 예를 들어, 4자리 비밀번호를 푸는 문제가 있다면 0000부터 시작해서 비밀번호가 맞을 때까지 모든 조합을 확인해보는 방법이다. 

 

---

2. Brute-Force(완전탐색)을 푸는 방법 

- 완전탐색 문제를 푸는 알고리즘은 다음과 같다.

 

▶ 순열

▶ 백트래킹

▶ BFS 

 

- 문제의 접근 방법에 따라 활용할 수 있는 방법이 위의 3가지로 나뉜다. 

 

---

3. 완전탐색을 구현하기 전에 

- 완전탐색을 구현할 때는, 다음의 요소들을 주의해야 한다. 

 

▶ 입력과 출력의 제한을 파악하자. 

   - 모든 경우의 수를 계산하는 방식이기 때문에, 알고리즘 문제의 입력과 출력제한을 파악해야한다. 

 

▶ 입출력 제한을 확인 후, 문제에 대한 접근방식을 생각한다. 

   - 단순한 for문, 수열, 재귀(백트래킹) 중 하나를 선택한다. 

 

▶ 이제 제출 후 맞기를 기도하자. 

   - 틀렸다면 어떤 부분에서 틀렸는지를 확인하고 그 부분을 극복하자. 

   - 입출력 제한에 걸린건지, 무한루프에 빠진건지, 잘못된 결과가 나온건지 등 확인하자. 

 

---

4. 시간계산하기

- 완전탐색 알고리즘의 경우, 모든 경우의 수를 확인하는 방식이기 때문에 시간계산을 우선 해야한다.

- 완전탐색의 문제의 경우 다음과 같은 시간복잡도를 가질 수 있다.  

- 일반적으로 컴퓨터는 1억번의 연산을 하는데 1초가 걸린다. 

 

▶ O(N)

   - N <= 1억

   - 1억개 경우의 수 연산까지 1초 

 

▶ O(N log N)

   - N <= 500만 

   - 5백만개 경우의 수 연산까지 1초 

 

▶ O(N^2)

   - N <= 1만 

   - 1만개 경우의 수 연산까지 1초 

 

▶ O(N!)

   - N <= 11

   - 11! 까지 연산하는데 1초 (12! 의 경우의 수를 구하면 5억 가까이 된다.)

---

5. 백트래킹 알고리즘

https://devraphy.tistory.com/87

Advanced Algorithm - Backtracking

 

 

---

[참고자료]

 

https://youtu.be/V_Z77_klksI