백트래킹 | 모든 경우의 수 탐색 알고리즘 완벽 정리
이 글의 핵심
백트래킹에 대한 실전 가이드입니다. 모든 경우의 수 탐색 알고리즘 완벽 정리 등을 예제와 함께 상세히 설명합니다.
들어가며
”모든 경우를 시도하되, 불가능하면 되돌아가기”
백트래킹은 모든 경우의 수를 탐색하되, 조건 불만족 시 즉시 포기하는 알고리즘입니다. DFS와 유사하지만 가지치기(Pruning)를 통해 불필요한 탐색을 건너뜁니다.
이 글을 읽으면
- 백트래킹의 핵심 패턴을 이해합니다
- 순열, 조합, 부분집합을 구현할 수 있습니다
- N-Queen, 스도쿠 같은 제약 만족 문제를 풉니다
- 가지치기로 성능을 최적화합니다
목차
사전 지식 (초보자를 위한 기초)
1. 재귀(Recursion) 복습
백트래킹은 재귀를 기반으로 합니다. 재귀가 낯설다면 먼저 이해하고 오세요.
# 재귀 예시: 1부터 n까지 출력
def print_numbers(n):
if n == 0: # 기저 조건 (멈추는 조건)
return
print_numbers(n - 1) # 재귀 호출 (자기 자신 호출)
print(n)
print_numbers(3)
# 출력:
# 1
# 2
# 3
# 실행 과정:
# print_numbers(3)
# → print_numbers(2)
# → print_numbers(1)
# → print_numbers(0) (멈춤)
# → print(1)
# → print(2)
# → print(3)2. 트리 구조 이해
백트래킹은 결정 트리(Decision Tree)를 탐색합니다.
예시: [1, 2, 3]에서 2개 선택하기
[]
/ | \
[1] [2] [3]
/ \ |
[1,2] [1,3] [2,3]
각 노드: 현재까지의 선택
각 가지: 다음 선택지
리프 노드: 최종 결과3. 경우의 수란?
경우의 수는 가능한 모든 경우를 세는 것입니다.
# 예시: [1, 2, 3]을 나열하는 모든 방법
# 순열 (순서 중요, 3! = 6가지)
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
# 조합 (순서 무관, 2개 선택 = 3가지)
[1, 2]
[1, 3]
[2, 3]
# 부분집합 (2³ = 8가지)
[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]4. 백트래킹의 핵심 아이디어
“미로 탈출”을 생각해보세요:
미로 탈출 전략:
1. 한 방향으로 계속 진행
2. 막다른 길이면 → 되돌아가기 (Backtrack)
3. 다른 방향 시도
4. 출구 찾을 때까지 반복
백트래킹도 똑같습니다:
1. 하나의 선택을 함
2. 조건을 만족하지 않으면 → 되돌아가기
3. 다른 선택 시도
4. 해를 찾을 때까지 반복코드로 표현:
def backtrack(선택들):
# 1. 해를 찾았으면 저장
if 조건_만족(선택들):
결과_저장(선택들)
return
# 2. 모든 선택지 시도
for 선택 in 가능한_선택들:
if 유효한_선택(선택): # 가지치기!
선택_추가(선택) # 선택
backtrack(선택들) # 다음 단계로
선택_제거(선택) # 되돌리기 (Backtrack)5. 가지치기(Pruning)란?
가지치기는 불가능한 경우를 미리 제거하는 것입니다.
# 예시: 합이 10인 3개 숫자 조합 찾기 (1~9 사용)
# ❌ 가지치기 없음 (모든 경우 탐색)
def no_pruning(nums, target):
# [1,2,3], [1,2,4], ..., [7,8,9]
# 총 84가지 모두 확인 (느림!)
pass
# ✅ 가지치기 있음 (불가능한 경우 제외)
def with_pruning(nums, current_sum, target):
# 현재 합이 이미 10을 넘으면 → 더 이상 탐색 안함!
if current_sum > target:
return # 가지치기!
# 예: [1, 2]까지 선택했고 합이 3
# 다음에 8을 선택하면 합이 11 → 10 초과
# 8, 9는 탐색할 필요 없음!가지치기의 효과:
가지치기 없음:
[]
/ | \
[1] [2] [3]
/ | \ / | \ / | \
... ... ... ... ...
(모든 경우 탐색 - 느림)
가지치기 있음:
[]
/ | \
[1] [2] [3]
/ | \ | X (합 초과, 가지치기!)
... X X
(불가능한 경우 제외 - 빠름!)6. 백트래킹 vs 완전 탐색
완전 탐색 (Brute Force):
- 모든 경우를 다 확인
- 느리지만 확실함
백트래킹:
- 조건을 만족하는 경우만 확인
- 가지치기로 빠름
# 완전 탐색: 모든 3자리 비밀번호 시도 (000~999)
for i in range(1000):
if try_password(i):
return i
# 최악: 1000번 시도
# 백트래킹: 조건 활용 (첫 자리가 5라는 힌트)
for i in range(500, 600): # 500~599만 시도
if try_password(i):
return i
# 최악: 100번 시도 (10배 빠름!)1. 백트래킹 기본
DFS vs 백트래킹
DFS (깊이 우선 탐색):
- 연결된 모든 노드를 방문
- 방문 여부만 체크
백트래킹:
- 조건을 만족하는 해만 탐색
- 조건 불만족 시 즉시 되돌아감 (가지치기)
# DFS: 모든 노드 방문
def dfs(node, visited):
visited.add(node)
for child in node.children:
if child not in visited:
dfs(child, visited)
# 백트래킹: 조건 체크 + 가지치기
def backtrack(state):
if is_solution(state):
add_solution(state)
return
for choice in get_choices(state):
if is_valid(choice): # 가지치기!
make_choice(choice)
backtrack(state)
undo_choice(choice) # 되돌리기백트래킹 템플릿
def backtrack_template(state, choices, result):
"""
백트래킹 범용 템플릿
"""
# 1. 종료 조건
if is_complete(state):
result.append(state.copy())
return
# 2. 가지치기 (조기 종료)
if not is_valid(state):
return
# 3. 선택 시도
for choice in choices:
# 선택
state.add(choice)
# 재귀
backtrack_template(state, choices, result)
# 되돌리기
state.remove(choice)2. 순열과 조합
순열 (Permutation)
정의: n개 중 r개를 순서를 고려하여 선택
예시: [1, 2, 3]에서 2개 선택 → [1,2], [1,3], [2,1], [2,3], [3,1], [3,2]
Python 구현
def permutations(arr, n):
"""
순열: nPr
- 순서 O, 중복 X
- 시간: O(n!)
"""
result = []
def backtrack(path, remaining):
if len(path) == n:
result.append(path[:])
return
for i in range(len(remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], arr)
return result
# 테스트
print(permutations([1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]C++ 구현
#include <vector>
#include <iostream>
using namespace std;
void permutationsHelper(
vector<int>& arr,
int n,
vector<int>& path,
vector<bool>& used,
vector<vector<int>>& result
) {
if (path.size() == n) {
result.push_back(path);
return;
}
for (int i = 0; i < arr.size(); ++i) {
if (!used[i]) {
used[i] = true;
path.push_back(arr[i]);
permutationsHelper(arr, n, path, used, result);
path.pop_back();
used[i] = false;
}
}
}
vector<vector<int>> permutations(vector<int>& arr, int n) {
vector<vector<int>> result;
vector<int> path;
vector<bool> used(arr.size(), false);
permutationsHelper(arr, n, path, used, result);
return result;
}
int main() {
vector<int> arr = {1, 2, 3};
auto result = permutations(arr, 2);
for (const auto& perm : result) {
for (int num : perm) {
cout << num << " ";
}
cout << "\n";
}
return 0;
}시간 복잡도: O(n!)
공간 복잡도: O(n)
조합 (Combination)
정의: n개 중 r개를 순서 무관하게 선택
예시: [1, 2, 3]에서 2개 선택 → [1,2], [1,3], [2,3]
Python 구현
def combinations(arr, n):
"""
조합: nCr
- 순서 X, 중복 X
- 시간: O(2ⁿ)
"""
result = []
def backtrack(start, path):
if len(path) == n:
result.append(path[:])
return
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# 테스트
print(combinations([1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 3]]C++ 구현
#include <vector>
#include <iostream>
using namespace std;
void combinationsHelper(
const vector<int>& arr,
int n,
int start,
vector<int>& path,
vector<vector<int>>& result
) {
if (path.size() == n) {
result.push_back(path);
return;
}
for (int i = start; i < arr.size(); ++i) {
path.push_back(arr[i]);
combinationsHelper(arr, n, i + 1, path, result);
path.pop_back();
}
}
vector<vector<int>> combinations(const vector<int>& arr, int n) {
vector<vector<int>> result;
vector<int> path;
combinationsHelper(arr, n, 0, path, result);
return result;
}
int main() {
vector<int> arr = {1, 2, 3};
auto result = combinations(arr, 2);
for (const auto& comb : result) {
for (int num : comb) {
cout << num << " ";
}
cout << "\n";
}
return 0;
}시간 복잡도: O(2ⁿ)
공간 복잡도: O(n)
부분집합 (Subset)
정의: 모든 가능한 부분집합 생성
Python 구현
def subsets(arr):
"""
모든 부분집합
- 시간: O(2ⁿ)
"""
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# 테스트
print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]3. N-Queen 문제
문제 설명
N×N 체스판에 N개의 퀸을 배치하되, 서로 공격할 수 없도록 배치합니다.
제약:
- 같은 행에 퀸 없음
- 같은 열에 퀸 없음
- 같은 대각선에 퀸 없음
Python 구현
def solve_n_queens(n):
"""
N-Queen 문제
- 백트래킹으로 모든 해 찾기
"""
result = []
board = [['.'] * n for _ in range(n)]
def is_valid(row, col):
# 같은 열 체크
for i in range(row):
if board[i][col] == 'Q':
return False
# 왼쪽 위 대각선
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 오른쪽 위 대각선
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(row):
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if is_valid(row, col):
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
backtrack(0)
return result
# 테스트
solutions = solve_n_queens(4)
print(f"{len(solutions)}개 해")
for i, sol in enumerate(solutions):
print(f"\n해 {i + 1}:")
for row in sol:
print(row)
# 출력:
# 2개 해
#
# 해 1:
# .Q..
# ...Q
# Q...
# ..Q.
#
# 해 2:
# ..Q.
# Q...
# ...Q
# .Q..최적화 버전 (Set 사용)
def solve_n_queens_optimized(n):
"""
N-Queen 최적화
- Set으로 O(1) 충돌 체크
"""
result = []
board = [['.'] * n for _ in range(n)]
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def backtrack(row):
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return result
# 테스트
solutions = solve_n_queens_optimized(8)
print(f"8-Queen: {len(solutions)}개 해") # 92개시간 복잡도: O(n!) — 가지치기로 실제는 훨씬 빠름
4. 고급 활용
1) 부분집합 합 (Subset Sum)
문제: 합이 target인 부분집합 찾기
Python 구현
def subset_sum(arr, target):
"""
부분집합 합 문제
- 가지치기: current_sum > target
"""
result = []
def backtrack(start, path, current_sum):
if current_sum == target:
result.append(path[:])
return
if current_sum > target:
return
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(i + 1, path, current_sum + arr[i])
path.pop()
backtrack(0, [], 0)
return result
# 테스트
arr = [1, 2, 3, 4, 5]
target = 5
print(subset_sum(arr, target))
# [[1, 4], [2, 3], [5]]2) 조합 합 (Combination Sum)
문제: LeetCode 39 - Combination Sum
특징: 같은 숫자를 여러 번 사용 가능
Python 구현
class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
result = []
def backtrack(start, path, current_sum):
if current_sum == target:
result.append(path[:])
return
if current_sum > target:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, current_sum + candidates[i])
path.pop()
backtrack(0, [], 0)
return result
# 테스트
sol = Solution()
print(sol.combinationSum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]3) 스도쿠 (Sudoku)
문제: LeetCode 37 - Sudoku Solver
Python 구현
def solve_sudoku(board):
"""
9x9 스도쿠 풀기
"""
def is_valid(row, col, num):
# 행 체크
if num in board[row]:
return False
# 열 체크
if num in [board[i][col] for i in range(9)]:
return False
# 3x3 박스 체크
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for i in range(box_row, box_row + 3):
for j in range(box_col, box_col + 3):
if board[i][j] == num:
return False
return True
def backtrack():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if is_valid(i, j, num):
board[i][j] = num
if backtrack():
return True
board[i][j] = '.'
return False
return True
backtrack()
return board
# 테스트
board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
solve_sudoku(board)
for row in board:
print(' '.join(row))4) 단어 검색 (Word Search)
Python 구현
class Solution:
def exist(self, board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def backtrack(r, c, idx):
if idx == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[idx]):
return False
temp = board[r][c]
board[r][c] = '#'
found = (backtrack(r + 1, c, idx + 1) or
backtrack(r - 1, c, idx + 1) or
backtrack(r, c + 1, idx + 1) or
backtrack(r, c - 1, idx + 1))
board[r][c] = temp
return found
for i in range(rows):
for j in range(cols):
if backtrack(i, j, 0):
return True
return False
# 테스트
sol = Solution()
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
print(sol.exist(board, "ABCCED")) # True
print(sol.exist(board, "SEE")) # True
print(sol.exist(board, "ABCB")) # False5. 실무 사례
사례 1: 작업 스케줄링 - 제약 만족
시나리오: 작업 시간과 의존성 제약을 만족하는 스케줄 찾기
Python 구현
from dataclasses import dataclass
@dataclass
class Task:
id: int
duration: int
dependencies: list[int]
def schedule_tasks(tasks, max_time):
"""
제약 만족 스케줄링
"""
n = len(tasks)
result = []
def is_valid(schedule, task_idx):
task = tasks[task_idx]
for dep_id in task.dependencies:
if dep_id not in schedule:
return False
current_time = sum(tasks[i].duration for i in schedule)
if current_time + task.duration > max_time:
return False
return True
def backtrack(schedule):
if len(schedule) == n:
result.append(schedule[:])
return
for i in range(n):
if i not in schedule and is_valid(schedule, i):
schedule.append(i)
backtrack(schedule)
schedule.pop()
backtrack([])
return result
# 테스트
tasks = [
Task(0, 2, []),
Task(1, 3, [0]),
Task(2, 1, [0]),
Task(3, 2, [1, 2]),
]
schedules = schedule_tasks(tasks, 10)
print(f"{len(schedules)}개 가능한 스케줄")
for schedule in schedules:
print([tasks[i].id for i in schedule])사례 2: 조합 최적화 - 배낭 문제
시나리오: 무게 제한 내에서 가치 최대화
Python 구현
def knapsack_backtrack(items, capacity):
"""
0-1 배낭 문제 (백트래킹)
- items: [(weight, value), ...]
"""
best_value = [0]
best_items = []
def backtrack(idx, current_weight, current_value, path):
if current_value > best_value[0]:
best_value[0] = current_value
best_items.clear()
best_items.extend(path)
if idx == len(items):
return
weight, value = items[idx]
if current_weight + weight <= capacity:
path.append(idx)
backtrack(idx + 1, current_weight + weight, current_value + value, path)
path.pop()
backtrack(idx + 1, current_weight, current_value, path)
backtrack(0, 0, 0, [])
return best_value[0], best_items
# 테스트
items = [(2, 3), (3, 4), (4, 5), (5, 6)]
capacity = 8
max_value, selected = knapsack_backtrack(items, capacity)
print(f"최대 가치: {max_value}")
print(f"선택한 아이템: {selected}")
# 최대 가치: 10
# 선택한 아이템: [0, 1, 2] (무게 2+3+4=9 X, 2+3=5로 재계산)사례 3: 경로 탐색 - 미로 탈출
시나리오: 미로에서 모든 가능한 경로 찾기
Python 구현
def find_all_paths(maze, start, end):
"""
미로 모든 경로 찾기
- 0: 통행 가능, 1: 벽
"""
rows, cols = len(maze), len(maze[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
result = []
def backtrack(r, c, path, visited):
if (r, c) == end:
result.append(path[:])
return
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
maze[nr][nc] == 0 and (nr, nc) not in visited):
visited.add((nr, nc))
path.append((nr, nc))
backtrack(nr, nc, path, visited)
path.pop()
visited.remove((nr, nc))
visited = {start}
backtrack(start[0], start[1], [start], visited)
return result
# 테스트
maze = [
[0, 0, 1],
[0, 0, 0],
[1, 0, 0]
]
start = (0, 0)
end = (2, 2)
paths = find_all_paths(maze, start, end)
print(f"{len(paths)}개 경로")
for path in paths:
print(path)6. 트러블슈팅
문제 1: 되돌리기 누락
증상: 상태가 복구되지 않아 잘못된 결과
# 잘못된 예
def backtrack_wrong(path):
if len(path) == n:
result.append(path) # path 참조 저장
return
for choice in choices:
path.append(choice)
backtrack_wrong(path)
# path.pop() 누락!해결:
def backtrack_correct(path):
if len(path) == n:
result.append(path[:]) # 복사본 저장
return
for choice in choices:
path.append(choice)
backtrack_correct(path)
path.pop() # 되돌리기문제 2: 가지치기 누락
증상: 불필요한 탐색으로 시간 초과
# 가지치기 없음
def backtrack_slow(current_sum, path):
if len(path) == n:
if current_sum == target:
result.append(path[:])
return
for num in arr:
path.append(num)
backtrack_slow(current_sum + num, path)
path.pop()해결: 조기 종료 추가
def backtrack_fast(start, current_sum, path):
if current_sum == target:
result.append(path[:])
return
if current_sum > target: # 가지치기!
return
for i in range(start, len(arr)):
path.append(arr[i])
backtrack_fast(i + 1, current_sum + arr[i], path)
path.pop()문제 3: 중복 결과
증상: 같은 조합이 여러 번 나옴
# 잘못된 예
def combinations_wrong(arr, n):
result = []
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for num in arr: # start 없음
path.append(num)
backtrack(path)
path.pop()
backtrack([])
return result
# [1,2,3], n=2 → [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]
# 중복: [1,2]와 [2,1]해결: start 인덱스 추가
def combinations_correct(arr, n):
result = []
def backtrack(start, path):
if len(path) == n:
result.append(path[:])
return
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result문제 4: 시간 초과 (TLE)
증상: n이 커지면 지수 시간 복잡도로 시간 초과
해결 1: 가지치기 강화
# 정렬 후 조기 종료
arr.sort()
def backtrack(start, current_sum, path):
if current_sum == target:
result.append(path[:])
return
for i in range(start, len(arr)):
if current_sum + arr[i] > target:
break # 정렬되어 있으므로 이후는 불필요
path.append(arr[i])
backtrack(i + 1, current_sum + arr[i], path)
path.pop()해결 2: DP로 전환
# 부분집합 합은 DP로도 해결 가능
def subset_sum_dp(arr, target):
dp = [False] * (target + 1)
dp[0] = True
for num in arr:
for i in range(target, num - 1, -1):
if dp[i - num]:
dp[i] = True
return dp[target]마무리
백트래킹은 모든 경우의 수를 탐색하되, 가지치기로 불필요한 탐색을 건너뛰는 알고리즘입니다.
핵심 패턴
def backtrack(state):
# 1. 종료 조건
if is_complete(state):
save_solution(state)
return
# 2. 가지치기
if not is_valid(state):
return
# 3. 선택 → 재귀 → 되돌리기
for choice in get_choices():
make_choice(choice)
backtrack(new_state)
undo_choice(choice)시간 복잡도
| 문제 | 시간 복잡도 | 가지치기 효과 |
|---|---|---|
| 순열 | O(n!) | 낮음 |
| 조합 | O(2ⁿ) | 중간 |
| 부분집합 합 | O(2ⁿ) | 높음 (정렬 시) |
| N-Queen | O(n!) | 매우 높음 |
| 스도쿠 | O(9^m) | 매우 높음 (m은 빈 칸) |
선택 가이드
| 문제 유형 | 알고리즘 |
|---|---|
| 모든 순열 | 백트래킹 |
| 모든 조합 | 백트래킹 |
| 최적 부분집합 | DP (가능하면) |
| 제약 만족 | 백트래킹 |
추천 문제
백준:
LeetCode:
다음 단계
- 동적 계획법: DP 완벽 정리
- BFS/DFS: BFS와 DFS 완벽 정리
- 그래프: 그래프 자료구조 완벽 정리
백트래킹은 가지치기가 핵심입니다. 조건을 빨리 판단할수록 성능이 좋아집니다.