출시·고도화 중
백트래킹 안내서 · 6/6
백트래킹은 코딩 테스트용 기법에 그치지 않습니다. 정규 표현식 엔진, SAT 솔버, 제약 프로그래밍 도구, 논리 프로그래밍 언어처럼 우리가 매일 쓰는 도구 안에서 돌아가고 있습니다. 이 장에서는 백트래킹이 쓰이는 곳과 실제 코드에서 자주 만나는 함정, 그리고 더 읽을거리를 정리합니다.
re, Java java.util.regex, JavaScript, PCRE 같은 엔진은 패턴의 선택지(|, *, +)를 하나씩 시도하고 실패하면 되돌아가는 백트래킹 방식입니다. 그래서 역참조 같은 강력한 기능을 지원하지만, 입력에 따라 지수 시간이 걸릴 수 있습니다.(a+)+$ 같은 패턴은 a를 나누는 방법이 지수 개라서, 끝이 맞지 않는 입력에서 엔진이 모든 분할을 시도합니다. 사용자가 입력한 문자열에 이런 패턴을 쓰면 서비스 거부 공격(ReDoS)이 됩니다.
import re
import time
pattern = re.compile(r"(a+)+$")
for n in (16, 18, 20, 22):
text = "a" * n + "!"
start = time.perf_counter()
pattern.match(text)
print(n, f"{time.perf_counter() - start:.3f}s")
# 글자 하나가 늘 때마다 시간이 약 두 배로 늘어납니다해결책은 중첩된 반복을 없애 a+$처럼 단순하게 쓰거나, 입력 길이를 제한하거나, 선형 시간을 보장하는 RE2 계열 엔진을 쓰는 것입니다.
Python의 기본 재귀 한도는 1000 안팎이라서 깊이가 수천인 탐색은 RecursionError가 납니다. sys.setrecursionlimit으로 한도를 올릴 수 있지만 C 스택이 넘칠 위험이 있으니, 깊은 탐색은 명시적 스택으로 바꾸는 편이 안전합니다.
def subsets_iterative(nums):
result = []
stack = [(0, [])] # (다음 인덱스, 부분해)
while stack:
i, path = stack.pop()
if i == len(nums):
result.append(path)
continue
stack.append((i + 1, path)) # 넣지 않는 가지
stack.append((i + 1, path + [nums[i]])) # 넣는 가지
return result
print(subsets_iterative([1, 2])) # [[1, 2], [1], [2], []]명시적 스택 방식은 되돌리기 대신 상태를 복사하므로 메모리를 더 씁니다. 깊이가 얕다면 재귀 쪽이 더 간단하고 빠릅니다.
단순한 순열, 조합, 곱집합이 필요하다면 표준 라이브러리가 더 빠르고 검증되어 있습니다. 직접 백트래킹을 쓰는 것은 중간에 가지치기가 필요할 때입니다.
from itertools import combinations, permutations, product
print(list(combinations("ABC", 2))) # [('A', 'B'), ('A', 'C'), ('B', 'C')]
print(len(list(permutations(range(4))))) # 24
print(list(product([0, 1], repeat=2))) # [(0, 0), (0, 1), (1, 0), (1, 1)]
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.
첫 댓글을 남겨 보세요.