완전탐색 (Brute Force) 상세 정리 및 응용 문제

1. 완전탐색이란?

완전탐색은 가능한 모든 후보해(해답)를 전부 탐색하여 문제를 해결하는 방법입니다.
말 그대로 '무식하게' 모든 경우를 시도해보는 방식이라서 구현이 쉽고 직관적입니다.

모든 가능한 경우의 수를 하나하나 확인하며 정답을 찾습니다.
입력 크기가 작거나 경우의 수가 제한적인 문제에 적합합니다.
시간복잡도가 매우 클 수 있으므로, 입력 크기에 따라 비효율적일 수 있습니다.

예를 들어, n개의 원소에서 모든 부분집합을 구하는 경우, 경우의 수는 2^n 으로 증가합니다.
따라서 n이 커지면 완전탐색만으로 문제를 해결하기 어려워 최적화 기법이 필요합니다.

2. 완전탐색 응용 문제 및 코드 (주석 포함)

1) N-Queen 문제

N×N 크기의 체스판에 N개의 퀸을 서로 공격하지 못하도록 놓는 모든 경우의 수를 찾는 문제입니다.
퀸은 가로, 세로, 대각선 방향으로 공격할 수 있기 때문에 서로 공격하는 위치에 놓이면 안 됩니다.

def solve_n_queens(n):
    board = [-1] * n  # 각 행에 놓인 퀸의 열 위치를 저장 (board[i] = j 는 i번째 행에 j열에 퀸이 있음)
    solutions = []  # 가능한 모든 해답을 저장할 리스트

    def is_valid(row, col):
        # 현재 row 행에 col 열에 퀸을 놓을 수 있는지 검사
        for i in range(row):
            # 같은 열에 퀸이 있으면 안됨
            if board[i] == col:
                return False
            # 대각선 공격 방지: 행 차이와 열 차이가 같으면 대각선에 있음
            if abs(board[i] - col) == row - i:
                return False
        return True

    def dfs(row):
        # 모든 행에 퀸을 놓았으면 하나의 해답 완성
        if row == n:
            solutions.append(board[:])  # 현재 퀸 위치를 복사해 저장
            return

        # 현재 행(row)에서 모든 열(col)에 퀸 놓기 시도
        for col in range(n):
            if is_valid(row, col):
                board[row] = col  # 퀸 놓기
                dfs(row + 1)      # 다음 행으로 이동하여 탐색
                # 백트래킹: 탐색 후 돌아와서 다음 열 시도

    dfs(0)  # 0행부터 시작
    return solutions

# 예시 출력 (4-Queen 문제)
print(solve_n_queens(4))

2) 부분 집합의 합 문제 (Subset Sum)

주어진 배열에서 일부 원소를 골라 합이 목표값(target)과 같은 부분집합이 있는지 확인하는 문제입니다.
완전탐색으로 각 원소를 포함하거나 포함하지 않는 경우를 모두 시도합니다.

def subset_sum(nums, target):
    def dfs(i, current_sum):
        # 목표 합에 도달하면 True 반환
        if current_sum == target:
            return True

        # 배열 끝에 도달했거나 현재 합이 초과하면 False 반환
        if i == len(nums) or current_sum > target:
            return False

        # 현재 원소를 포함하는 경우와 포함하지 않는 경우 모두 탐색
        return dfs(i + 1, current_sum + nums[i]) or dfs(i + 1, current_sum)

    return dfs(0, 0)

# 예시 출력
print(subset_sum([3, 34, 4, 12, 5, 2], 9))  # True (4 + 5 = 9)

3) 문자열의 모든 순열 구하기

주어진 문자열의 문자들을 재배열하여 만들 수 있는 모든 순열을 찾는 문제입니다.
완전탐색 + 백트래킹 기법을 이용해 중복 없이 모든 순열을 생성합니다.

def permute(s):
    results = []
    s = list(s)  # 문자열을 리스트로 변환 (문자 교환을 위해)

    def dfs(start):
        # 모든 문자를 고정하면 순열 완성
        if start == len(s) - 1:
            results.append(''.join(s))  # 리스트를 문자열로 변환하여 저장
            return

        for i in range(start, len(s)):
            # 현재 위치와 i 위치 문자를 바꿔가며 순열 생성
            s[start], s[i] = s[i], s[start]
            dfs(start + 1)  # 다음 위치로 이동
            s[start], s[i] = s[i], s[start]  # 백트래킹: 원상복구

    dfs(0)
    return results

# 예시 출력
print(permute("abc"))

3. 완전탐색의 시간복잡도 및 한계

완전탐색은 보통 모든 경우를 탐색하므로 경우의 수에 따라 시간이 급격히 증가합니다.
예를 들어, N-Queen 문제는 최악의 경우 O(N!) 정도 복잡도가 됩니다.
부분집합 문제는 2^n, 순열 문제도 n! 복잡도를 가집니다.
입력 크기가 작을 때 완전탐색은 강력하지만, 큰 입력에 대해서는 백트래킹, DP, 분할 정복 등으로 최적화해야 합니다.

728x90