완전 탐색(Brute Force)

in Blog / 알고리즘

백준 문제 풀때, ‘일단 모든 경우의 수를 다 대입해보자’ 라는 생각으로 문제 접근할 때가 있다. 이런 접근 방법이 완전 탐색이다. 당연 시간 복잡도는 높다.

완전 탐색의 특징은 아래와 같다.

  • 모든 경우의 수를 조건에 맞는지 확인
  • 무식하지만, 입력 크기가 작다면 이런 접근도 괜찮다
  • 시간 복잡도가 큼
  • 재귀, 반복문, 백트래킹, 순열/조합, DFS/BFS 등을 활용함함

그러면 예제로 비슷한 경우를 따져보자자

단순 반복문 활용

예제 : 1부터 100까지의 숫자 중 7의 배수 찾기

for i in range(1, 101):
    if i % 7 == 0:
        print(i, end=" ")

순열과 조합(itertools 활용)

예제 : 순열(Permutation) - 모든 순서를 고려한 경우

from itertools import permutations

arr = [1, 2, 3]
perm = list(permutations(arr, 2))  # 2개씩 순서 고려하여 나열
print(perm)
# 결과: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

예제 : 조합(Combination) - 순서는 고려하지 않고 특정 개수만큼 선택

from itertools import combinations

arr = [1, 2, 3]
comb = list(combinations(arr, 2))  # 2개씩 선택 (순서 상관없음)
print(comb)
# 결과: [(1, 2), (1, 3), (2, 3)]

재귀함수 활용

예제 : 1부터 N까지 숫자의 모든 조합 출력

def dfs(path, depth, n):
    if depth == n:
        print(path)
        return
    
    for i in range(1, n+1):
        if i not in path:  # 중복 방지
            dfs(path + [i], depth + 1, n)

dfs([], 0, 3)

백트래킹(Backtracking)

예제 : N-Queen 문제 (8x8 체스판에서 퀸 8개 배치)

def is_valid(board, row, col):
    for i in range(row):
        if board[i] == col or abs(board[i] - col) == abs(i - row):
            return False
    return True

def solve_n_queens(n, board=[], row=0):
    if row == n:
        print(board)
        return
    
    for col in range(n):
        if is_valid(board, row, col):
            solve_n_queens(n, board + [col], row + 1)

solve_n_queens(4)

이렇게 완전 탐색의 경우의 수를 알아보았다. 그렇다면 탐색 방법의 특징과 시간 복잡도를 알아보자. 아래 표를 참고하면 된다.

탐색 방법설명시간 복잡도
완전탐색모든 경우 탐색O(N!) (순열)
백트래킹가지치기 최적화O(N!) (최적화됨)
BFS/DFS그래프 탐색O(V+E)
이진 탐색정렬된 데이터에서 탐색O(log N)

완전탐색 특성상 유용하지 않을것 같지만 앞으로 나열하는 경우에는 유용할수도 있겠다. 작은 범위의 모든 경우를 확인할 때, 정확한 최적해를 구해야 할 때, 모든 조합을 확인해야 할때(ex: 비밀번호 크래킹)나 백트래킹 적용 정 접근할때

© 2022 JeongHwan Yun.