[WEEK01] 완전 탐색

완전 탐색

완전 탐색(Brute Force)은 가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 기법이다. 직관적이고 구현이 간단하지만, 경우의 수가 많아질수록 성능이 급격히 저하될 수 있다.

완전 탐색 기법

부르트-포스(Brute-Force) 기법

• 모든 가능한 경우를 무식하게 전부 확인하는 방법
• 예제: 비밀번호 크래킹, 문자열 검색(브루트 포스 알고리즘)

# 예제: 문자열에서 특정 패턴 찾기 (브루트 포스)
def brute_force_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            return i  # 패턴이 발견된 시작 위치 반환
    return -1

print(brute_force_search("abcdef", "cd"))  # 2

백트래킹(Backtracking)

• 불필요한 경우를 조기에 배제하여 탐색 속도를 높이는 방법
• 가지치기 : 답을 찾는 과정에서 이 경로가 답이 아니라고 판단되면 버리고 다른 경로를 탐색함
• 대표적인 예제: N-Queen 문제, 순열 생성

# 예제: 부분집합 해결 (백트래킹)
def backtrack(start, path, nums, result):
    result.append(path)
    
    for i in range(start, len(nums)):
        # 현재 숫자를 포함한 경로 생성
        backtrack(i + 1, path + [nums[i]], nums, result)

def subsets(nums):
    result = []
    backtrack(0, [], nums, result)
    return result

# 예제 사용
nums = [1, 2, 3]
all_subsets = subsets(nums)
print(all_subsets)

비트마스크(Bitmask)

• 정수를 이진수로 표현하여 부분집합을 탐색하는 방법
• 이진수를 사용하는 컴퓨터의 연산 방식을 이용하는 방식
• 대표적인 예제: 부분집합 생성, 조합 문제 해결

• AND(&) : 둘 다 1이면 1
• OR(|) : 둘 중 1개만 1이면 1
• NOT(~) : 1이면 0, 0이면 1
• XOR(^) : 둘의 관계가 다르면 1, 같으면 0
• Shift(<<, >>) : A를 좌/우측으로 B 비트만큼 이동

# 예제: 집합 {1, 2, 3}의 모든 부분집합 생성 (비트마스크)
def generate_subsets(arr):
    n = len(arr)
    subsets = []
    for i in range(1 << n):  # 2^n 개의 부분집합
        subset = [arr[j] for j in range(n) if (i & (1 << j))]
        subsets.append(subset)
    return subsets

print(generate_subsets([1, 2, 3]))

순열(Permutation)

• 주어진 원소들의 모든 순서를 고려하는 방법
•  서로 다른 n개의 원소에서 r개를 중복 없이 골라 순서대로 나열하는 방식
• 대표적인 예제: 여행하는 외판원 문제(TSP)

from itertools import permutations

# 예제: [1, 2, 3]의 모든 순열 생성
arr = [1, 2, 3]
print(list(permutations(arr)))

재귀 함수(Recursion)

• 함수가 자기 자신을 호출하며 문제를 해결하는 방식
• 대표적인 예제: 피보나치 수열, 하노이의 탑

# 예제: 피보나치 수열 (재귀)
def fibo(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibo(5))  # 5

BFS / DFS

• 그래프 탐색에서 활용되는 완전 탐색 기법
• BFS(Breadth-First Search): 너비 우선 탐색
• DFS(Depth-First Search): 깊이 우선 탐색

from collections import deque

# BFS 예제
def bfs(graph, start):
    queue = deque([start])
    visited = set()
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# DFS 예제
def dfs(graph, node, visited=set()):
    if node not in visited:
        visited.add(node)
        print(node, end=" ")
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# 그래프 정의
graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [7],
    4: [],
    5: [],
    6: [],
    7: []
}

print("BFS:")
bfs(graph, 1)
print("\nDFS:")
dfs(graph, 1)

완전 탐색의 시간 복잡도

• 경우의 수가 많아지면 시간이 급격히 증가하는 단점이 있음
• 일반적인 완전 탐색 알고리즘의 시간 복잡도:
  • 순열, 조합: O(n!)
  • 부분집합 탐색(비트마스크): O(2ⁿ)
  • DFS/BFS: O(V+E) (그래프 탐색 시)

완전 탐색 최적화 방법

• 백트래킹으로 불필요한 탐색 줄이기
• 메모이제이션을 활용하여 중복 연산 방지
• 정렬을 활용하여 탐색 범위 축소

📌 정리

완전 탐색은 직관적이지만 경우의 수가 많을 경우 비효율적일 수 있다. 따라서 백트래킹, 비트마스크 등의 기법을 활용하여 최적화할 필요가 있다.