백트래킹은 코딩 테스트용 기법에 그치지 않습니다. 정규 표현식 엔진, SAT 솔버, 제약 프로그래밍 도구, 논리 프로그래밍 언어처럼 우리가 매일 쓰는 도구 안에서 돌아가고 있습니다. 이 장에서는 백트래킹이 쓰이는 곳과 실제 코드에서 자주 만나는 함정, 그리고 더 읽을거리를 정리합니다.
백트래킹이 쓰이는 곳
- 정규 표현식 엔진: Python
re, Java java.util.regex, JavaScript, PCRE 같은 엔진은 패턴의 선택지(|, *, +)를 하나씩 시도하고 실패하면 되돌아가는 백트래킹 방식입니다. 그래서 역참조 같은 강력한 기능을 지원하지만, 입력에 따라 지수 시간이 걸릴 수 있습니다. - SAT 솔버와 DPLL: 불리언 변수에 값을 하나씩 정하고 모순이 나오면 되돌아가는 DPLL 알고리즘이 현대 SAT 솔버(CDCL)의 바탕입니다. 하드웨어 검증, 패키지 의존성 해결에 쓰입니다.
- 제약 프로그래밍: Google OR-Tools의 CP-SAT 같은 솔버는 시간표, 근무표, 생산 일정을 변수와 제약으로 표현해 탐색하며, 제약 전파로 가지를 미리 잘라 냅니다.
- 논리 프로그래밍: Prolog는 규칙을 위에서부터 시도하고 실패하면 다음 규칙으로 되돌아가는 것이 실행 모델 그 자체입니다.
- 퍼즐과 게임: 스도쿠, 크로스워드, 정확한 덮개 문제(Knuth의 Dancing Links) 풀이기가 대표적입니다.
- 파서: PEG 파서와 일부 재귀 하강 파서는 문법 규칙을 차례로 시도하고 실패하면 입력 위치를 되돌립니다.
함정 1: 정규 표현식의 파국적 백트래킹
(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 계열 엔진을 쓰는 것입니다.
함정 2: 재귀 깊이와 복사 비용
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], []]
명시적 스택 방식은 되돌리기 대신 상태를 복사하므로 메모리를 더 씁니다. 깊이가 얕다면 재귀 쪽이 더 간단하고 빠릅니다.
함정 3: 이미 있는 도구를 다시 만들기
단순한 순열, 조합, 곱집합이 필요하다면 표준 라이브러리가 더 빠르고 검증되어 있습니다. 직접 백트래킹을 쓰는 것은 중간에 가지치기가 필요할 때입니다.
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)]
그 밖에 주의할 점
- 되돌리기를 빠뜨리거나 순서를 틀리면 다른 가지에 상태가 새어 들어가 결과가 조용히 틀립니다. 선택과 되돌리기 코드를 항상 짝으로 씁니다.
- 가지치기 조건이 너무 강하면 정답 가지까지 잘라 냅니다. 작은 입력에서는 완전 탐색 결과와 비교하는 테스트를 두면 안전합니다.
- 입력 크기가 커질 수 있다면 최악의 탐색량을 미리 추정하고, 시간 제한이나 노드 수 제한을 두어 서비스가 멈추지 않게 합니다.
- 제약이 복잡한 실제 일정 문제는 직접 구현하기보다 CP-SAT 같은 솔버에 맡기는 것이 대개 낫습니다.
정리
- 백트래킹은 정규 표현식, SAT 솔버, 제약 프로그래밍, Prolog처럼 실무 도구의 핵심 엔진으로 쓰입니다.
- 파국적 백트래킹, 재귀 깊이, 되돌리기 누락이 실무에서 가장 흔한 문제입니다.
- 표준 라이브러리와 전용 솔버로 해결되는 일은 그쪽에 맡기고, 가지치기가 필요한 곳에 직접 구현합니다.
더 읽을거리
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.