완전 탐색(Brute Force Search | Exhaustive Search)

완전 탐색 또는 브루트 포스라고 불리는 이 알고리즘은 이름 그대로 모든 경우의 수를 다 탐색해 보는 것을 말한다.

 

예를 들어 입력으로 들어온 N 개의 수 중, 서로 다른 숫자를 더했을 때 짝수가 되게 하는 경우의 수를 구하는 코드를 작성해야 될 때 완전 탐색을 이용하면 이렇게 작성할 수 있다.

n=int(input())
l=list(map(int,input().split()))
cnt=0
for i in range(n):
    for g in range(n):
        if i!=g and (l[i]+l[g])%2==0:
            cnt+=1


print(cnt)

이렇게 작성하면 위 문제에서 원하는 답을 구할 수 있고, 해당 코드의 시간복잡도는 O(N^2)가 된다.

 

해당 문제 같은 경우 O(N)에 계산하는 방법이 존재하는데, 이처럼 완전 탐색의 경우 그 방법보다 더 빠른 방법이 있는 경우가 높아서 잘 사용되지는 않는다.

하지만 완전 탐색으로 못 풀거 같지만 케이스 분류를 잘하면 완전 탐색으로 풀 수 있는 문제가 존재하는데, 이처럼 몇몇 경우에서 완전 탐색을 요구하는 문제가 나올 수 있다.