[알고리즘] 완전 탐색

가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 방식의 알고리즘입니다.

가장 직관적이고 단순하지만, 계산량이 많아질 수 있기 때문에 입력 크기가 클 경우에는 성능 문제가 발생합니다.

---

✅ 완전 탐색의 기본 개념

• 정의: 문제의 해답을 얻기 위해 모든 경우의 수를 하나하나 확인하는 방식.
• 특징:
  • 가장 단순한 방법
  • 정확한 해를 보장
  • 효율성은 떨어질 수 있음

---

✅ 예시 문제와 접근 방식

예시 1: 1~100 사이의 숫자 중에서 어떤 수를 맞추는 게임

• 완전 탐색: 1부터 100까지 전부 시도하면서 정답을 찾는다.

예시 2: 주어진 배열에서 두 수의 합이 특정 값이 되는 조합 찾기

arr = [1, 2, 3, 4, 5]
target = 6

for i in range(len(arr)):
    for j in range(i+1, len(arr)):
        if arr[i] + arr[j] == target:
            print(arr[i], arr[j])

• 시간 복잡도: O(n²)

---

✅ 완전 탐색의 주요 방식

분류 설명 예시

순열(Permutation)	n개의 원소 중에서 순서를 고려하여 r개 선택	itertools.permutations()
조합(Combination)	n개의 원소 중에서 순서를 고려하지 않고 r개 선택	itertools.combinations()
부분집합(Powerset)	주어진 집합의 모든 부분집합 탐색	비트마스크 방식 or 재귀
중복순열 / 중복조합	같은 원소를 중복해서 선택할 수 있는 경우	itertools.product() 등

---

✅ 파이썬 표준 라이브러리 활용

from itertools import permutations, combinations, product

# 순열
list(permutations([1,2,3], 2))  
# 조합
list(combinations([1,2,3], 2))
# 중복순열
list(product([1,2,3], repeat=2))

 

---

✅ 장단점

장점

• 구현이 쉽고 확실한 정답을 찾을 수 있음
• 문제 이해에 유용함 (기초 로직 설계 시)

단점

• 입력 크기가 조금만 커져도 계산량이 기하급수적으로 증가 (→ 시간 초과 위험)
• 효율적인 알고리즘이 필요할 경우 비효율적

---

✅ 언제 사용하는가?

• 입력 크기(n)가 작을 때 (예: n ≤ 10 ~ 20)
• 모든 경우의 수를 다 확인해야 할 때
• 최적화된 알고리즘이 복잡하거나 아직 생각나지 않을 때 기본 로직 확인용으로 초안 작성 시

---

✅ 활용 가능한 전략

• 조기 종료(Break)
• 백트래킹(조건 만족 안 될 경우 탐색 중지)
• 가지치기 (조건문으로 불필요한 경우 생략)

---

완전 탐색(Brute-force) 문제에서 자주 사용되는 코드 패턴

=> 경우의 수 생성 + 조건 검사 + 결과 처리

이 구조를 기반으로 여러 유형의 완전 탐색 문제에 응용할 수 있으며, 대표적으로 다음과 같은 패턴들이 자주 쓰입니다.

---

✅ 1. 순열(모든 순서 경우의 수)

사용 예: n개 중 r개를 뽑아 순서대로 나열할 때

from itertools import permutations

arr = [1, 2, 3]
for p in permutations(arr, 2):  # (1,2), (1,3), (2,1), ...
    print(p)

직접 구현 (백트래킹):

def permute(path, used):
    if len(path) == r:
        print(path)
        return
    for i in range(len(arr)):
        if not used[i]:
            used[i] = True
            permute(path + [arr[i]], used)
            used[i] = False

arr = [1, 2, 3]
r = 2
permute([], [False] * len(arr))

---

✅ 2. 조합(순서 상관 없는 선택)

from itertools import combinations

arr = [1, 2, 3]
for c in combinations(arr, 2):  # (1,2), (1,3), (2,3)
    print(c)

---

✅ 3. 부분 집합 (Power Set)

# 비트마스크 방법
arr = [1, 2, 3]
n = len(arr)

for i in range(1 << n):  # 2^n 개
    subset = [arr[j] for j in range(n) if (i & (1 << j))]
    print(subset)

# 재귀적 부분집합 생성
def subset(idx, current):
    if idx == len(arr):
        print(current)
        return
    subset(idx + 1, current + [arr[idx]])  # 포함
    subset(idx + 1, current)               # 미포함

arr = [1, 2, 3]
subset(0, [])

---

✅ 4. 중복 순열 (product)

from itertools import product

arr = [1, 2]
for p in product(arr, repeat=2):  # (1,1), (1,2), (2,1), (2,2)
    print(p)

---

✅ 5. 이중/삼중 루프 (완전 탐색의 기본 구조)

# 배열 내 두 수의 합이 특정 값이 되는 경우
arr = [1, 2, 3, 4, 5]
target = 6
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if arr[i] + arr[j] == target:
            print(arr[i], arr[j])

# 최대값 찾기
max_val = -float('inf')
for i in range(N):
    for j in range(M):
        # 특정 조건 계산
        if 조건:
            max_val = max(max_val, 계산결과)

---

✅ 6. DFS/BFS를 이용한 완전 탐색

# DFS로 모든 경로 탐색 (예: 미로 문제)
def dfs(x, y, visited):
    if (x, y) == goal:
        count += 1
        return
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 유효한좌표(nx, ny) and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, visited)
            visited[nx][ny] = False

---

✅ 7. 조건 기반 조기 종료 (가지치기)

def search(path):
    if 조건을 만족하지 않으면:
        return  # 가지치기
    if 최종 조건:
        결과 저장
        return
    for 다음 경우의 수:
        search(다음 path)

---

✨ 요약: 문제 유형별 대표 패턴

문제 유형 대표 코드 패턴

순열	itertools.permutations 또는 DFS
조합	itertools.combinations 또는 DFS
부분집합	비트마스크 또는 재귀
완전탐색(2중루프)	중첩 for문
경로 탐색	DFS / BFS
조건 만족 여부	if 조건문 + 가지치기