완전탐색 알고리즘 (Exhaustive Search)

개요

완전탐색 알고리즘은 가능한 모든 경우의 수를 모두 탐색하여 문제의 해답을 찾는 방법입니다. 이러한 접근 방식은 Brute Force라고도 불리며, 직관적이고 구현이 간단하지만, 경우의 수가 많아질수록 시간과 자원 소모가 크게 증가하는 단점이 있습니다.

---

완전탐색 기법의 종류

완전탐색을 구현하는 데에는 여러 가지 기법이 활용됩니다:

1. 단순 Brute Force 기법

반복문과 조건문을 통해 가능한 모든 경우를 직접 확인하는 방법입니다. 예를 들어, 4자리 암호로 구성된 자물쇠를 풀기 위해 0000부터 9999까지 모든 조합을 시도하는 것이 이에 해당합니다.

def brute_force_password():
    for i in range(10000):
        attempt = f"{i:04}"
        if try_password(attempt):
            return attempt

2. 순열 (Permutation)

서로 다른 n개의 원소를 일렬로 나열하는 모든 경우를 생성하는 방법입니다. 이는 재귀 호출을 통해 구현할 수 있습니다.

from itertools import permutations

data = ['A', 'B', 'C']
for perm in permutations(data):
    print(perm)

3. 조합 (Combination)

n개의 원소 중에서 r개를 선택하는 조합을 생성하는 방법입니다. 이는 itertools의 combinations를 이용해 쉽게 구현할 수 있습니다.

from itertools import combinations

data = ['A', 'B', 'C', 'D']
for comb in combinations(data, 2):
    print(comb)

4. 중복 순열 (Product)

중복을 허용하는 순열을 생성하는 방법입니다. itertools의 product를 사용하면 간단하게 구현할 수 있습니다.

from itertools import product

data = ['A', 'B', 'C']
for prod in product(data, repeat=2):
    print(prod)

5. 재귀 호출 (Recursion)

함수가 자기 자신을 호출하여 문제를 해결하는 방식입니다. 예를 들어, 피보나치 수열을 재귀적으로 계산할 수 있습니다.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

6. 비트마스크 (Bitmask)

이진수를 활용하여 부분집합을 표현하고 탐색하는 방법입니다. 각 비트가 원소의 포함 여부를 나타내므로, 부분집합 생성에 유용합니다.

n = 3
for i in range(1 << n):
    subset = []
    for j in range(n):
        if i & (1 << j):
            subset.append(j)
    print(subset)

7. BFS와 DFS

• BFS (Breadth-First Search): 너비 우선 탐색으로, 큐를 사용하여 구현하며, 최단 경로 탐색에 유용합니다.
• DFS (Depth-First Search): 깊이 우선 탐색으로, 스택 또는 재귀를 사용하여 구현하며, 모든 경로를 탐색하는 데 적합합니다.

# DFS 예시
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

---

itertools 모듈 소개

Python의 itertools 모듈은 반복 가능한 객체의 조합을 생성하는 데 유용한 다양한 함수들을 제공합니다.

주요 함수

• permutations(iterable, r): 순열 생성
• combinations(iterable, r): 조합 생성
• combinations_with_replacement(iterable, r): 중복 허용 조합 생성
• product(iterable, repeat=n): 중복 순열 생성
• chain(iterables): 여러 iterable을 하나로 연결
• cycle(iterable): iterable을 무한히 반복
• repeat(element, times): 특정 원소를 지정한 횟수만큼 반복

예제: itertools를 활용한 조합과 순열

from itertools import permutations, combinations

data = ['A', 'B', 'C']
print("순열:")
for perm in permutations(data):
    print(perm)

print("\n조합:")
for comb in combinations(data, 2):
    print(comb)

---

완전탐색의 장단점

장점:

• 구현이 비교적 간단하며, 모든 경우를 탐색하므로 정확한 해답을 보장합니다.

단점:

• 경우의 수가 많을 경우 시간 복잡도가 급격히 증가하여 비효율적일 수 있습니다.

---

결론

완전탐색 알고리즘은 모든 가능한 경우를 탐색하여 해답을 찾는 방법으로, 문제의 규모가 작거나 가능한 경우의 수가 적을 때 유용하게 사용됩니다. 그러나 경우의 수가 많아질수록 비효율적일 수 있으므로, 이러한 상황에서는 다른 최적화된 알고리즘을 고려하는 것이 좋습니다.