백트래킹: 막다른 길에서 되돌아가기
무식하게 다 해보기(Brute Force)는 너무 느립니다. 가다가 '이 길은 아닌가 봐' 싶으면 과감하게 돌아오는 용기. N-Queen 문제가 대표적입니다.
무식하게 다 해보기(Brute Force)는 너무 느립니다. 가다가 '이 길은 아닌가 봐' 싶으면 과감하게 돌아오는 용기. N-Queen 문제가 대표적입니다.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.

나는 비전공자 출신이라 알고리즘 문제를 만나면 항상 주눅부터 들었다. 특히 재귀(Recursion)가 나오는 순간 "아, 나는 안 되나 봐"라는 생각이 자동으로 떠올랐다. 그러던 어느 날, 알고리즘 공부를 하다가 N-Queen 문제를 만났다. "8x8 체스판에 퀸 8개를 서로 공격하지 못하게 놓아라." 문제를 읽고 나서 든 생각은 단 하나였다. "이거 그냥 모든 경우의 수를 다 해보면 되는 거 아냐?"
그래서 일단 코드를 짰다. 64칸 중 8개를 고르는 조합을 만들어서 하나하나 체크하는 Brute Force 방식이었다. 돌려봤다. 프로그램이 멈췄다. 3분이 지나도 답이 안 나왔다. 계산기를 두드려봤더니 경우의 수가 44억이 넘었다. "아... 이렇게 풀면 안 되는 거구나." 그때 처음 깨달았다. "똑똑하게 포기하는 법"을 알아야 한다는 걸.
그게 바로 백트래킹(Backtracking)이었다.
처음 백트래킹을 배울 때 가장 혼란스러웠던 건, "이거 그냥 DFS(깊이 우선 탐색) 아니야?"라는 의문이었다. 재귀 호출로 깊게 들어가는 것도 같고, 스택 구조도 같고, 뭔가 비슷해 보였다. 그런데 찾아보니 미묘한 차이가 있었다. DFS는 "갈 수 있는 곳은 다 간다"는 마인드지만, 백트래킹은 "이 길은 가망이 없으니까 아예 안 간다"는 마인드였다. 이 차이가 엄청난 성능 차이를 만들어냈다.
백트래킹은 단순히 "뒤로 돌아가기"가 아니라 "가지치기(Pruning)"를 포함한 탐색 방식이었다. 나무를 키우듯 가능성 있는 가지만 뻗어나가고, 죽은 가지는 과감하게 잘라내는 것. 이 개념이 와닿고 나서부터 많은 문제가 풀리기 시작했다.
백트래킹을 이해했다고 생각했던 순간, 정규표현식(Regex)을 공부하다가 ReDOS 공격이라는 걸 알게 됐다. (a+)+b 같은 패턴에 aaaaaaa... 문자열을 넣으면 서버 CPU가 100%를 찍고 죽는다는 내용이었다. "정규식 엔진도 백트래킹을 쓰는구나!" 그 순간 깨달았다. 백트래킹은 단순히 알고리즘 문제풀이 기법이 아니라, 우리가 매일 쓰는 수많은 시스템의 핵심 메커니즘이었다.
Cloudflare가 전 세계에 502 에러를 뿌렸던 사건도 이 백트래킹 기반 정규식 엔진의 폭주 때문이었다는 걸 알고는 충격을 받았다. "아, 이 알고리즘은 진짜 쓰이는 거구나." 그래서 나는 백트래킹을 "빨리 포기하는 기술"이라고 정리해봤다. 완벽하게 다 해보려고 하면 시간이 폭발한다. 하지만 "이 길은 안 될 것 같아"라는 직감이 정확하다면, 그 길을 아예 안 가는 것만으로도 엄청난 효율을 얻는다.
모든 선택은 거대한 트리(Tree)로 표현할 수 있다. 루트 노드는 아무 선택도 하지 않은 초기 상태이고, 가지(Branch)는 우리가 할 수 있는 선택들이며, 단말 노드(Leaf)는 최종 결과다. 백트래킹은 이 트리를 깊이 우선 탐색(DFS) 방식으로 순회하되, 멍청하게 모든 노드를 방문하지 않는다.
특정 노드에 도착했을 때 "이 길이 가망이 있는가?(Promising)"를 판단한다. Yes라면 자식 노드로 계속 내려가고, No라면 즉시 부모 노드로 되돌아간다. 이게 바로 가지치기(Pruning)다. 이 판단 함수(isPromising())를 얼마나 똑똑하게 짜느냐가 알고리즘의 성능을 결정한다.
비유하자면 이렇다. 미로를 탐험하는데, 특정 통로에 들어서자마자 "어? 여기 막혀 있네"라는 표지판이 보인다면, 끝까지 가보지 않고 바로 돌아오는 것이다. 이 "표지판 읽는 능력"이 백트래킹의 핵심이다.
N-Queen 문제는 1848년 체스 작곡가 막스 베첼(Max Bezzel)이 처음 제안했다. 하지만 이 문제가 유명해진 건 카를 프리드리히 가우스(Carl Friedrich Gauss)가 1850년에 이 문제에 꽂혔기 때문이다. 수학의 황태자라 불리던 가우스는 펜과 종이만으로 이 문제를 풀려고 시도했다. 그때는 컴퓨터가 없었으니 가우스의 두뇌가 곧 CPU였다.
그는 72개의 해답을 찾아냈다. 하지만 실제 정답은 92개였다. 천하의 가우스조차 사람인지라 실수를 피할 수 없었던 것이다. 만약 가우스에게 백트래킹 알고리즘과 컴퓨터가 있었다면, 0.001초 만에 92개를 다 찾았을 것이다. 이 일화는 알고리즘적 사고(Algorithmic Thinking)가 천재의 직관보다 더 강력할 수 있음을 보여준다.
나는 이 이야기를 알고 나서 위안을 받았다. "가우스도 못 찾은 걸 내가 못 찾는 게 당연하지." 하지만 동시에 깨달았다. "그래도 나는 컴퓨터가 있잖아." 알고리즘을 제대로 이해하고 구현할 수 있다면, 우리는 가우스를 뛰어넘을 수 있다.
N-Queen 문제를 다시 보자. 8x8 체스판에서 무식하게 모든 경우를 따지면 $64C8 \approx 44$억 가지다. 컴퓨터로도 몇 분이 걸린다. 하지만 백트래킹을 쓰면 수천 가지로 줄어든다.
def solve_n_queens(n):
board = [-1] * n # board[row] = col
results = []
def is_safe(row, col):
for prev_row in range(row):
prev_col = board[prev_row]
# 세로 열 겹침 or 대각선 겹침
if prev_col == col or abs(prev_col - col) == abs(prev_row - row):
return False
return True
def backtrack(row):
if row == n:
results.append(list(board)) # 해답 발견!
return
for col in range(n):
if is_safe(row, col):
board[row] = col
backtrack(row + 1) # 재귀 호출
board[row] = -1 # 되돌리기 (Backtrack)
backtrack(0)
return results
여기서 핵심은 is_safe() 함수다. 이 함수가 "가망성 판단"을 한다. 만약 어떤 칸에 퀸을 놓았을 때 이미 놓인 퀸과 충돌한다면, 그 칸은 아예 시도하지 않는다. 이게 가지치기다.
그리고 또 하나 중요한 건 board[row] = -1 이 부분이다. 재귀 호출에서 빠져나왔을 때 상태를 원상복구(Clean up)해야 다음 탐색에 영향을 주지 않는다. 이 부분을 빼먹는 게 주니어 개발자들이 가장 많이 하는 실수다. 나도 처음에 이거 빼먹고 3시간 디버깅했던 기억이 있다.
스도쿠도 백트래킹의 전형적인 예제다. 사람이 푸는 방식 그대로다. 다만 컴퓨터는 초당 수백만 번 썼다 지웠다를 반복할 뿐이다.
def solve_sudoku(board):
empty = find_empty(board)
if not empty:
return True # 빈칸이 없으면 완성!
row, col = empty
for num in range(1, 10):
if is_valid(board, num, (row, col)):
board[row][col] = num # 시도
if solve_sudoku(board): # 재귀
return True
board[row][col] = 0 # 실패! 되돌리기
return False # 1~9 다 안 됨 -> 이전 단계로 Back
def is_valid(board, num, pos):
# 가로, 세로, 3x3 박스 체크
# ... (생략)
return True
board[row][col] = 0 이 한 줄이 바로 백트래킹이다. 이 줄이 없으면 알고리즘은 막다른 길에서 영원히 멈춰버린다.
N-Queen 문제를 풀다가 "시간 초과"가 떴던 경험이 있다. 배열 방식으로는 한계가 있었다. 그때 알게 된 게 비트마스크(Bitmask) 최적화였다. 처음에는 "비트 연산? 너무 어려운데"라고 생각했지만, 막상 써보니 엄청나게 빨랐다. 배열 방식보다 10배 이상 빠른 속도를 경험했다.
def solve(row, cols, d1, d2):
if row == N:
return 1
count = 0
# 놓을 수 있는 자리들을 비트 연산으로 한 번에 계산
available = ~(cols | d1 | d2) & ((1 << N) - 1)
while available:
# 가장 오른쪽의 1인 비트(위치)를 가져옴
curr = available & -available
available -= curr
# 재귀 호출 (비트 시프트로 대각선 처리)
count += solve(row + 1, cols | curr, (d1 | curr) << 1, (d2 | curr) >> 1)
return count
이 방식은 메모리 접근을 최소화하고 CPU의 비트 연산기(ALU)를 극한으로 활용한다. 처음에는 이해가 안 갔지만, "cols는 세로 열 점유 상태", "d1은 왼쪽 대각선 점유 상태", "d2는 오른쪽 대각선 점유 상태"라고 정리해본 후 코드가 눈에 들어왔다. 이런 최적화를 경험하고 나서 비트 연산의 매력에 빠졌다.
우리는 매일 백트래킹을 쓰고 있다. 바로 정규표현식(Regex) 엔진이다. a*b 패턴을 찾을 때, 엔진은 a를 최대한 많이 매칭해보고(Greedy), 뒤에 b가 없으면 하나씩 a를 뱉어내며(Backtrack) 다시 시도한다.
그런데 여기서 문제가 생긴다. 만약 패턴을 (a+)+b처럼 짜면 어떻게 될까? 백트래킹의 경우의 수가 지수적으로 폭발(Exponential Blowup)한다. 공격자가 aaaaaaaaa... 같은 문자열을 보내면, 서버 CPU는 이걸 매칭하느라 100%를 찍고 멈춰버린다. 이것이 ReDOS(Regular Expression Denial of Service) 공격이다.
실제로 Cloudflare가 전 세계에 502 Bad Gateway를 띄웠던 원인도 이 백트래킹 기반 정규식 엔진의 폭주 때문이었다. 이 사건을 알고 나서 나는 정규식을 쓸 때 항상 조심하게 됐다. "이 패턴이 백트래킹을 많이 유발하지는 않을까?" 그래서 Go나 Rust의 정규식 엔진은 백트래킹 대신 Thompson's Construction (NFA) 방식을 써서 $O(N)$을 보장한다. 이런 차이를 알고 나니 언어 선택도 달라졌다.
백트래킹은 훌륭하지만 만능은 아니다. 최악의 경우, 가지치기가 거의 안 된다면? 결국 모든 경우의 수를 다 뒤져야 하므로 $O(2^N)$ 또는 $O(N!)$이라는 절망적인 시간이 걸린다. 이런 문제들을 NP-Complete 문제라고 한다. 외판원 순회 문제(TSP) 같은 거다. N이 100만 넘어가면 우주가 멸망할 때까지 답이 안 나온다.
이럴 때는 백트래킹을 포기하고, "적당히 괜찮은 답"을 찾는 유전 알고리즘(Genetic Algorithm)이나 메타휴리스틱을 써야 한다. 완벽함(Optimum)을 포기하면 속도(Speed)를 얻을 수 있으니까. 나는 이 트레이드오프를 받아들이고 나서 "모든 문제를 완벽하게 풀 필요는 없구나"라고 생각하게 됐다.
처음 배울 때 이 둘을 엄청 헷갈려했다. "둘 다 재귀 쓰는데 뭐가 달라?" 하지만 정리해본 결과, 목적이 완전히 달랐다.
| 특징 | 백트래킹 | 동적계획법 (DP) |
|---|---|---|
| 목적 | 모든 가능한 해 탐색 | 최적해 또는 개수 구하기 |
| 방식 | 가보고 아니면 돌아오기 | 작은 문제 답 저장해서 재사용 |
| 메모리 | 스택만 씀. 적음 | 테이블 만듦. 많이 씀 |
| 예시 | N-Queen, 미로 찾기 | 피보나치, 배낭 문제(Knapsack) |
백트래킹은 "길 찾기", DP는 "최적화"라고 정리해봤다. 0/1 배낭 문제는 둘 다 가능한데, 보통 성능 때문에 DP로 푼다. 하지만 무게(W)가 엄청 크고 N이 작다면 백트래킹이 더 빠를 수도 있다. 이게 알고리즘의 묘미다.
board[row] = -1 같은 한 줄이 알고리즘을 살린다.