브루트 포스(Brute Force) 알고리즘

  • Brute(무식한) + Force(힘) 의 조합어로 무식하게 모든 경우의 수를 다 탐색하여 문제를 해결하는 방법
  • 모든 경우의 수를 다 탐색하기 때문에 완전탐색이라고도 한다
  • 효율은 매우 떨어지지만 100% 확률로 정답을 찾아낸다
  • 선형구조는 순차탐색, 비선형구조는 DFS/BFS 등을 사용한다
  • 모든 경우의 수를 다 탐색해야 하기 때문에 시간복잡도가 O(n!) or O(2n)가 되기 때문에 문제에서 n은 매우 작게 제시되는 편이다

구현방법

1. 반복문(for문) 사용

  • 반복문을 사용하여 모든 경우를 순차탐색하여 정답을 도출한다
n = int(input())
for i in range(n):
    if n%i==0:
        print(i)

2. 재귀(DFS)

  • 완전 탐색을 할 때 원소를 앞에서부터 차례로 돌면서 해당 원소를 포함할지 포함하지 않을지 선택하여 각 각의 경우를 재귀적으로 호출한다
  • 원소를 포함할지 포함하지 않을지 선택해 나가며 상태공간트리가 완성된다
    (문제에 조건이 주어진다면 이 과정에서 백트래킹을 적용할 수도 있다)
    (1) 해당 원소를 포함할지(True), 포함하지 않을지(False) 선택하는 유형 (= 비트마스크)
    (2) 현재 레벨에서 어떤 원소를 선택할지(1 or 2 or 3 등 여러개 선택지 중 선택) 유형

3. BFS

4. 순열

  • n개 중에 r개만 선택해 탐색하는 경우에는 순열을 사용할 수 있다