[Python] 완전 탐색(Brute Force)

핵심 개념

완전 탐색(Brute Force)은 가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 방법이다. 최적화 없이 모든 경우를 시도하기 때문에 구현이 간단하지만, 경우의 수가 많아지면 비효율적일 수 있다.

 

시간 복잡도

완전 탐색의 시간 복잡도는 일반적으로 \( O(N!) \) 또는 \( O(2^N) \) 등 매우 높은 편이다. 예를 들어, n개의 요소가 있을 때 가능한 모든 순열을 탐색하는 경우 \( O(N!) \)이 된다. 따라서 입력 크기가 커질수록 실행 시간이 급격히 증가한다.

 

동작방식 & 구현

완전 탐색은 보통 다음과 같은 방식으로 동작한다.

1. 가능한 모든 경우의 수를 생성한다.
2. 각 경우가 문제의 조건을 만족하는지 확인한다.
3. 원하는 결과를 찾으면 반환하거나 최적의 해를 갱신한다.

 

활용 가능한 문제 유형

완전 탐색은 다양한 문제에서 활용할 수 있다.

• 순열과 조합 문제: 가능한 모든 순열이나 조합을 생성해 정답을 찾는 문제
• 부분 집합 생성: 특정 조건을 만족하는 부분 집합 찾기
• 비밀번호 크래킹: 가능한 모든 비밀번호를 대입해 찾는 방식
• 최적의 경로 찾기: 외판원 문제(TSP)와 같이 모든 경로를 탐색해 최적의 해를 찾는 문제

 

예제 코드(Python)

def generate_subsets(arr, subset=[], index=0):
    if index == len(arr):
        print(subset)
        return
    
    # 현재 요소를 포함하지 않는 경우
    generate_subsets(arr, subset, index + 1)
    
    # 현재 요소를 포함하는 경우
    generate_subsets(arr, subset + [arr[index]], index + 1)

# 예제 실행
arr = [1, 2, 3]
generate_subsets(arr)

 

결론

완전 탐색은 간단하고 직관적인 알고리즘이지만, 경우의 수가 많아질수록 비효율적이 될 수 있다. 따라서 입력 크기가 작거나 최적화가 필요하지 않은 경우에 유용하게 사용할 수 있다. 보다 효율적인 해결 방법이 필요한 경우 백트래킹, 동적 계획법(DP), 분할 정복 등의 기법과 함께 사용하면 좋다.