[ 완전탐색 ] 완전탐색(Brute Force) 알고리즘 이론정리

1. 완전탐색(Brute Force)이란?

완전탐색(Brute Force)은 가능한 모든 경우의 수를 하나하나 전부 시도해보며 정답을 찾는 알고리즘 기법입니다. 특정 조건을 만족하는 정답을 찾기 위해 문제 공간 전체를 탐색하며, 경우에 따라선 매우 많은 연산이 필요할 수 있지만, 구현이 단순하다는 장점이 있습니다.

쉽게 말해, 답이 될 수 있는 모든 후보를 만들어보고 그중 정답 조건을 만족하는 것을 찾는 방법입니다. 정확한 해를 보장하며, 복잡한 최적화보다는 조건을 만족하는 답이 있는지만 찾는 문제에 주로 사용됩니다.

 

2. 완전탐색은 언제 사용하는가?

완전탐색은 시간복잡도가 크기 때문에 다음과 같은 상황에서 주로 사용됩니다:

• 입력의 크기 N이 작을 때 (일반적으로 N <= 10~15)
• 최적의 해를 구할 필요 없이 가능한 해 하나를 찾거나, 조건을 만족하는 해의 개수를 세면 되는 문제
• 다른 알고리즘(그리디, DP 등)으로 풀기 어려운 문제이지만 완탐으로는 풀 수 있는 문제
• 제한 시간 내에 모든 경우의 수를 탐색해도 시간 초과가 나지 않는 경우

즉, 완전탐색은 알고리즘 문제 풀이의 첫 번째 관문으로, 문제를 처음 마주했을 때 가장 먼저 시도해볼 수 있는 전략입니다.

 

3. 완전탐색 기법 종류 및 사용법

완전탐색을 구현할 때는 다음과 같은 여러 가지 방식이 존재합니다:

3-1. 반복문 중첩

이중, 삼중 루프를 통해 가능한 모든 경우를 단순하게 열거하는 방식입니다. 예를 들어 1부터 9까지 숫자 중 세 개를 선택하는 모든 경우의 수를 확인하는 경우, 세 개의 for문을 중첩해 사용할 수 있습니다.

3-2. 재귀함수

반복문으로 표현하기 어려운 깊이 우선 탐색을 할 때 재귀함수를 자주 사용합니다. 특히 순열, 조합, 부분집합을 만들 때 유용하며, 방문 처리 및 백트래킹 요소도 함께 다루게 됩니다.

3-3. itertools 라이브러리 사용

Python의 표준 라이브러리인 itertools를 활용하면 간결하게 완전탐색을 구현할 수 있습니다.

• permutations: 순열
• combinations: 조합
• product: 중복순열
• combinations_with_replacement: 중복조합

3-4. 비트마스킹

부분집합 탐색 시 비트마스크를 활용하면 효율적입니다. N개의 원소가 있다면, 모든 부분집합은 2^N개이고 이를 0부터 2^N-1까지의 이진수로 표현해 탐색합니다.

 

 

4. 기법별 예시 설명

4-1. 순열(permutation) 완탐

from itertools import permutations
for p in permutations([1, 2, 3]):
    print(p)

4-2. 조합(combination) 완탐

from itertools import combinations
for c in combinations([1, 2, 3, 4], 2):
    print(c)

4-3. 부분집합 완탐 (비트마스크)

arr = [1, 2, 3]
N = len(arr)
for i in range(1 << N):  # 0 ~ 2^N-1
    subset = []
    for j in range(N):
        if i & (1 << j):
            subset.append(arr[j])
    print(subset)

4-4. DFS 기반 완전탐색 (예: 백트래킹)

def dfs(depth):
    if depth == N:
        print(path)
        return
    for i in range(1, N+1):
        if not visited[i]:
            visited[i] = True
            path.append(i)
            dfs(depth + 1)
            path.pop()
            visited[i] = False

 

 

5. 완전탐색 구현 팁

• visited 배열을 활용하여 중복 탐색 방지
• 가능한 경우의 수를 세기 전에 조건을 미리 거르는 가지치기 시도
• 경우의 수를 수식으로 계산해보고 탐색이 가능한지 판단
• 시뮬레이션 + 완전탐색 문제의 경우, 상태(맵, 좌표 등)를 잘 추적해야 함
• 문제 조건 중 "최대 N은 10 이하" 같은 문구가 나오면 완탐을 의심