백트래킹은 언제 쓰나요?

모든 경우의 수를 탐색해야 할 때 사용합니다. N-Queen, 순열, 조합 등.

DFS는 모든 노드 방문, 백트래킹은 조건 불만족 시 가지치기(Pruning).

최악 O(2ⁿ) ~ O(n!). 가지치기로 실제는 훨씬 빠름.

[2026] 백트래킹 | 모든 경우의 수 탐색 알고리즘 완벽 정리

2026년 3월 28일 · 35분 읽기 · 수정 2026년 4월 7일 중급 튜토리얼

이 글의 핵심

백트래킹: 모든 경우의 수 탐색 알고리즘 백트래킹 기본·순열과 조합.

들어가며

”모든 경우를 시도하되, 불가능하면 되돌아가기”

백트래킹은 모든 경우의 수를 탐색하되, 조건 불만족 시 즉시 포기하는 알고리즘입니다. DFS와 유사하지만 가지치기(Pruning)를 통해 불필요한 탐색을 건너뜁니다.

이 글을 읽으면

백트래킹의 핵심 패턴을 이해합니다
순열, 조합, 부분집합을 구현할 수 있습니다
N-Queen, 스도쿠 같은 제약 만족 문제를 풉니다
가지치기로 성능을 최적화합니다

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

사전 지식 (초보자를 위한 기초)

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)를 탐색합니다. 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

예시: [1, 2, 3]에서 2개 선택하기
                    []
          /          |          \
        [1]         [2]         [3]
       /   \         |
    [1,2] [1,3]   [2,3]
각 노드: 현재까지의 선택
각 가지: 다음 선택지
리프 노드: 최종 결과

3. 경우의 수란?

경우의 수는 가능한 모든 경우를 세는 것입니다. 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 예시: [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. 백트래킹의 핵심 아이디어

“미로 탈출”을 생각해보세요: 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

미로 탈출 전략:
1. 한 방향으로 계속 진행
2. 막다른 길이면 → 되돌아가기 (Backtrack)
3. 다른 방향 시도
4. 출구 찾을 때까지 반복
백트래킹도 똑같습니다:
1. 하나의 선택을 함
2. 조건을 만족하지 않으면 → 되돌아가기
3. 다른 선택 시도
4. 해를 찾을 때까지 반복

코드로 표현: 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def backtrack(선택들):
    # 1. 해를 찾았으면 저장
    if 조건_만족(선택들):
        결과_저장(선택들)
        return
    
    # 2. 모든 선택지 시도
    for 선택 in 가능한_선택들:
        if 유효한_선택(선택):  # 가지치기!
            선택_추가(선택)      # 선택
            backtrack(선택들)    # 다음 단계로
            선택_제거(선택)      # 되돌리기 (Backtrack)

5. 가지치기(Pruning)란?

가지치기는 불가능한 경우를 미리 제거하는 것입니다. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 예시: 합이 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는 탐색할 필요 없음!

가지치기의 효과: 다음은 text를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

가지치기 없음:
              []
       /      |      \
     [1]    [2]    [3]
    / | \   / | \   / | \
  .... .... .... .... ...
  (모든 경우 탐색 - 느림)
가지치기 있음:
              []
       /      |      \
     [1]    [2]    [3]
    / | \    |      X (합 초과, 가지치기!)
  .... X     X
  (불가능한 경우 제외 - 빠름!)

6. 백트래킹 vs 완전 탐색

완전 탐색 (Brute Force):

모든 경우를 다 확인
느리지만 확실함 백트래킹:
조건을 만족하는 경우만 확인
가지치기로 빠름 아래 코드는 python를 사용한 구현 예제입니다. 에러 처리를 통해 안정성을 확보합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 완전 탐색: 모든 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 (깊이 우선 탐색):

연결된 모든 노드를 방문
방문 여부만 체크 백트래킹:
조건을 만족하는 해만 탐색
조건 불만족 시 즉시 되돌아감 (가지치기) 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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)  # 되돌리기

백트래킹 템플릿

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 구현

다음은 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++ 구현

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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 구현

다음은 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 구현

다음은 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 사용)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 구현

다음은 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 구현

다음은 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 구현

다음은 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)

문제: LeetCode 79 - Word Search

Python 구현

다음은 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"))    # False

5. 실무 사례

사례 1: 작업 스케줄링 - 제약 만족

시나리오: 작업 시간과 의존성 제약을 만족하는 스케줄 찾기

Python 구현

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 구현

다음은 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 구현

다음은 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: 되돌리기 누락

증상: 상태가 복구되지 않아 잘못된 결과 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 잘못된 예
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() 누락!

해결: 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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: 가지치기 누락

증상: 불필요한 탐색으로 시간 초과 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 가지치기 없음
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()

해결: 조기 종료 추가 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 중복 결과

증상: 같은 조합이 여러 번 나옴 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 잘못된 예
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 인덱스 추가 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 가지치기 강화 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 정렬 후 조기 종료
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로 전환 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 부분집합 합은 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]

마무리

백트래킹은 모든 경우의 수를 탐색하되, 가지치기로 불필요한 탐색을 건너뛰는 알고리즘입니다.

핵심 패턴

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 (가능하면)
제약 만족	백트래킹

다음 단계

동적 계획법: DP 완벽 정리
BFS/DFS: BFS와 DFS 완벽 정리
그래프: 그래프 자료구조 완벽 정리 백트래킹은 가지치기가 핵심입니다. 조건을 빨리 판단할수록 성능이 좋아집니다.

이 글의 핵심

들어가며

”모든 경우를 시도하되, 불가능하면 되돌아가기”

이 글을 읽으면

코딩 테스트 준비하며 깨달은 것

목차

사전 지식 (초보자를 위한 기초)

1. 재귀(Recursion) 복습

2. 트리 구조 이해

3. 경우의 수란?

4. 백트래킹의 핵심 아이디어

5. 가지치기(Pruning)란?

6. 백트래킹 vs 완전 탐색

1. 백트래킹 기본

DFS vs 백트래킹

백트래킹 템플릿

2. 순열과 조합

순열 (Permutation)

Python 구현

C++ 구현

조합 (Combination)

Python 구현

C++ 구현

부분집합 (Subset)

Python 구현

3. N-Queen 문제

문제 설명

Python 구현

최적화 버전 (Set 사용)

시간 복잡도: O(n!) — 가지치기로 실제는 훨씬 빠름

4. 고급 활용

1) 부분집합 합 (Subset Sum)

Python 구현

2) 조합 합 (Combination Sum)

Python 구현

3) 스도쿠 (Sudoku)

Python 구현

4) 단어 검색 (Word Search)

Python 구현

5. 실무 사례

사례 1: 작업 스케줄링 - 제약 만족

Python 구현

사례 2: 조합 최적화 - 배낭 문제

Python 구현

사례 3: 경로 탐색 - 미로 탈출

Python 구현

6. 트러블슈팅

문제 1: 되돌리기 누락

문제 2: 가지치기 누락

문제 3: 중복 결과

문제 4: 시간 초과 (TLE)

마무리

핵심 패턴

시간 복잡도

선택 가이드

추천 문제

다음 단계