TildAlice

백트래킹(Backtracking) 실전 풀이 전략 – N-Queen부터 순열/조합 생성까지

Updated Feb 6, 2026

백트래킹이란 무엇인가?

백트래킹(Backtracking)은 가능한 모든 경우의 수를 탐색하되, 조건에 맞지 않으면 즉시 되돌아가는 알고리즘 기법이다. 완전 탐색(Brute Force)의 비효율을 개선한 방법으로, 코딩테스트에서 가장 빈번하게 출제되는 유형 중 하나다.

핵심 아이디어는 간단하다:

  1. 선택: 현재 단계에서 가능한 선택지 중 하나를 고른다
  2. 검증: 해당 선택이 제약 조건을 만족하는지 확인한다
  3. 진행 또는 되돌림: 조건을 만족하면 다음 단계로 진행하고, 만족하지 않으면 이전 상태로 되돌아간다(backtrack)

백트래킹의 본질은 “가지치기(pruning)”다. 탐색 트리에서 유망하지 않은 가지를 일찍 잘라내어 탐색 공간을 줄인다.

완전 탐색 vs 백트래킹 비교

구분 완전 탐색(Brute Force) 백트래킹(Backtracking)
탐색 범위 모든 경우의 수 유망한 경우만 탐색
가지치기 없음 있음
시간 효율 낮음 상대적으로 높음
구현 방식 중첩 반복문, 재귀 재귀 + 조건 검사
적용 상황 경우의 수가 적을 때 경우의 수가 많지만 제약 조건이 있을 때

백트래킹의 일반적인 코드 구조

def backtrack(state, choices):
    # 기저 조건: 답을 찾았거나 탐색이 끝난 경우
    if is_solution(state):
        result.append(state[:])  # 현재 상태를 결과에 추가
        return

    for choice in choices:
        if is_valid(state, choice):   # 가지치기 조건
            state.append(choice)       # 선택
            backtrack(state, choices)   # 재귀 탐색
            state.pop()                # 되돌림 (backtrack)

이 템플릿을 기억해두면 대부분의 백트래킹 문제에 적용할 수 있다.

난이도별 접근법 차이

백트래킹 문제는 난이도에 따라 접근 방식이 달라진다.

난이도 핵심 포인트 대표 문제
쉬움 기본 재귀 구조 이해, 단순 순열/조합 생성 부분집합 생성, 순열 생성
보통 가지치기 조건 설계, 중복 제거 처리 N-Queen, 조합의 합
어려움 복합 제약 조건, 상태 공간 최적화, 비트마스킹 활용 스도쿠 풀기, 단어 검색 II

순열(Permutation) 생성

기본 원리

nn개의 원소에서 rr개를 순서를 고려하여 나열하는 모든 경우를 구하는 문제다.

순열의 수는 다음과 같다:

P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n-r)!}

  • nn: 전체 원소의 개수
  • rr: 선택할 원소의 개수
  • n!n!: nn의 팩토리얼 (n×(n−1)×⋯×1n \times (n-1) \times \cdots \times 1)

예를 들어 [1,2,3][1, 2, 3]에서 2개를 뽑는 순열의 수는 P(3,2)=3!1!=6P(3, 2) = \frac{3!}{1!} = 6이다.

Python 구현

def permutations(nums, r):
    """n개의 원소에서 r개를 뽑는 순열 생성"""
    result = []
    used = [False] * len(nums)  # 각 원소의 사용 여부 추적

    def backtrack(path):
        # 기저 조건: r개를 모두 선택했으면 결과에 추가
        if len(path) == r:
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:       # 이미 사용한 원소는 건너뛰기
                continue

            used[i] = True    # 원소 사용 표시
            path.append(nums[i])

            backtrack(path)   # 다음 원소 선택으로 진행

            path.pop()        # 되돌림
            used[i] = False   # 사용 표시 해제

    backtrack([])
    return result


# 실행 예시
nums = [1, 2, 3]
print(permutations(nums, 2))

출력:

[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

동작 과정 시각화

[1, 2, 3]에서 2개를 뽑는 순열의 탐색 트리:

              []
          /    |    \
        [1]   [2]   [3]
        / \   / \   / \
     [1,2][1,3] [2,1][2,3] [3,1][3,2]

각 리프 노드가 하나의 순열이 된다.

중복 순열 처리

입력에 중복 원소가 있을 때(예: [1, 1, 2]) 중복된 순열을 제거해야 한다.

def permutations_unique(nums):
    """중복 원소가 있는 경우의 순열 (중복 제거)"""
    result = []
    nums.sort()  # 정렬이 핵심: 같은 값을 인접하게 모은다
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            # 핵심 가지치기: 같은 값인데 이전 것을 아직 안 썼으면 건너뛰기
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result


# 실행 예시
print(permutations_unique([1, 1, 2]))

출력:

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

가지치기 핵심: nums[i] == nums[i-1] and not used[i-1] 조건은 “같은 값의 원소들 사이에서 앞의 것을 먼저 사용해야 한다”는 규칙을 강제한다. 이를 통해 동일한 순열이 여러 번 생성되는 것을 방지한다.

복잡도 분석

  • 시간 복잡도: O(n!×n)O(n! \times n) — 최대 n!n!개의 순열을 생성하며, 각 순열을 복사하는 데 O(n)O(n)
  • 공간 복잡도: O(n)O(n) — 재귀 호출 스택 깊이 + used 배열

조합(Combination) 생성

기본 원리

nn개의 원소에서 rr개를 순서를 고려하지 않고 뽑는 모든 경우를 구하는 문제다.

조합의 수는 다음과 같다:

C(n,r)=(nr)=n!r!(n−r)!C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

  • nn: 전체 원소의 개수
  • rr: 선택할 원소의 개수
  • r!r!: 순열에서 순서를 무시하기 위해 나누는 값

순열과의 핵심 차이는 탐색 시작 인덱스다. 순열은 매번 0부터 탐색하지만, 조합은 현재 선택한 인덱스의 다음부터 탐색한다.

Python 구현

def combinations(nums, r):
    """n개의 원소에서 r개를 뽑는 조합 생성"""
    result = []

    def backtrack(start, path):
        # 기저 조건: r개를 모두 선택
        if len(path) == r:
            result.append(path[:])
            return

        # start부터 탐색하여 중복 선택 방지 및 순서 강제
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)  # i+1부터 탐색 (자기 자신 제외)
            path.pop()

    backtrack(0, [])
    return result


# 실행 예시
nums = [1, 2, 3, 4]
print(combinations(nums, 2))

출력:

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

순열 vs 조합 코드 비교

구분 순열 조합
반복 시작점 range(0, n) range(start, n)
재귀 호출 시 backtrack(path) backtrack(i + 1, path)
중복 방지 used 배열 start 인덱스
[1,2]와 [2,1] 서로 다른 결과 같은 결과 (하나만 생성)

가지치기로 성능 향상

남은 원소의 수가 필요한 수보다 적으면 더 이상 탐색할 필요가 없다.

def combinations_optimized(nums, r):
    """가지치기가 적용된 조합 생성"""
    result = []
    n = len(nums)

    def backtrack(start, path):
        if len(path) == r:
            result.append(path[:])
            return

        # 가지치기: 남은 원소 수가 부족하면 탐색 중단
        # 필요한 원소 수: r - len(path)
        # 사용 가능한 원소 수: n - i
        for i in range(start, n - (r - len(path)) + 1):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

n - (r - len(path)) + 1이 반복 상한이 되는 이유: 현재까지 len(path)개를 골랐고 r - len(path)개가 더 필요하다. 인덱스 i부터 끝까지 남은 원소가 n - i개이므로, n - i >= r - len(path)여야 한다. 이를 정리하면 i <= n - (r - len(path))가 된다.

복잡도 분석

  • 시간 복잡도: O((nr)×r)O\left(\binom{n}{r} \times r\right) — 조합의 수만큼 생성하며, 각각 O(r)O(r)로 복사
  • 공간 복잡도: O(r)O(r) — 재귀 호출 스택 깊이

부분집합(Subset) 생성

기본 원리

nn개의 원소로 만들 수 있는 모든 부분집합을 구하는 문제다. 각 원소에 대해 “포함한다 / 포함하지 않는다” 두 가지 선택이 있으므로 전체 부분집합의 수는 2n2^n개다.

Python 구현

def subsets(nums):
    """모든 부분집합 생성"""
    result = []

    def backtrack(start, path):
        # 매 단계가 유효한 부분집합이므로 바로 결과에 추가
        result.append(path[:])

        for i in range(start, len(nums)):
            path.append(nums[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]]

동작 과정 시각화

backtrack(0, [])          → 결과: []
  backtrack(1, [1])       → 결과: [1]
    backtrack(2, [1,2])   → 결과: [1,2]
      backtrack(3, [1,2,3]) → 결과: [1,2,3]
    backtrack(3, [1,3])   → 결과: [1,3]
  backtrack(2, [2])       → 결과: [2]
    backtrack(3, [2,3])   → 결과: [2,3]
  backtrack(3, [3])       → 결과: [3]

조합과의 차이점은 기저 조건이 없다는 것이다. 매 재귀 호출마다 현재 상태를 결과에 추가한다.

복잡도 분석

  • 시간 복잡도: O(2n×n)O(2^n \times n) — 2n2^n개의 부분집합, 각각 복사에 O(n)O(n)
  • 공간 복잡도: O(n)O(n) — 재귀 호출 스택 깊이

N-Queen 문제 (중급 핵심)

문제 정의

N×NN \times N 체스판에 NN개의 퀸을 서로 공격할 수 없도록 배치하는 모든 경우의 수를 구하는 문제다.

퀸은 같은 행, 같은 열, 같은 대각선에 있는 말을 공격할 수 있다.

핵심 아이디어

  • 각 행에 퀸을 하나씩 배치한다 (행 충돌 자동 해결)
  • 열 충돌 검사: cols 집합으로 O(1)O(1) 확인
  • 대각선 충돌 검사:
  • 좌상→우하 대각선: 같은 대각선 위의 칸은 row - col 값이 동일
  • 우상→좌하 대각선: 같은 대각선 위의 칸은 row + col 값이 동일

대각선 판별 공식의 원리: 좌상→우하 대각선에서는 행과 열이 같은 방향으로 증가하므로 차이가 일정하고, 우상→좌하 대각선에서는 행이 증가할 때 열이 감소하므로 합이 일정하다.

Python 구현

def solve_n_queens(n):
    """N-Queen 문제의 모든 해를 구한다"""
    results = []

    # 충돌 검사용 집합 (O(1) 조회)
    cols = set()       # 사용 중인 열
    diag1 = set()      # 좌상→우하 대각선 (row - col)
    diag2 = set()      # 우상→좌하 대각선 (row + col)

    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        # 기저 조건: 모든 행에 퀸을 배치 완료
        if row == n:
            # 보드 상태를 문자열로 변환하여 저장
            results.append([''.join(r) for r in board])
            return

        for col in range(n):
            # 가지치기: 열 또는 대각선 충돌 시 건너뛰기
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue

            # 퀸 배치
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = 'Q'

            backtrack(row + 1)  # 다음 행으로 진행

            # 되돌림
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
            board[row][col] = '.'

    backtrack(0)
    return results


# 실행 예시: 4-Queen
solutions = solve_n_queens(4)
for i, sol in enumerate(solutions):
    print(f"해 {i + 1}:")
    for row in sol:
        print(f"  {row}")
    print()

print(f"총 {len(solutions)}개의 해")

출력:

해 1:
  .Q..
  ...Q
  Q...
  ..Q.

해 2:
  ..Q.
  Q...
  ...Q
  .Q..

총 2개의 해

4-Queen 탐색 과정 상세

row 0: col=0에 Q 배치 → [Q, -, -, -]
  row 1: col=0 (열 충돌) → skip
         col=1 (대각선 충돌: 0-0=0, 1-1=0) → skip
         col=2에 Q 배치 → [Q, -, Q, -]  (오류: 대각선!)
         col=2 (대각선 충돌: 0+0=0, 1+2=3, OK?) → ...

실제로는 row 0, col 0부터 시작해:
  row 1에서 col=2,3만 가능 → col=2 시도
    row 2에서 모든 열 충돌 → 백트래킹!
  row 1에서 col=3 시도
    row 2에서 col=1만 가능
      row 3에서 모든 열 충돌 → 백트래킹!

row 0: col=1에 Q 배치
  row 1: col=3에 Q 배치
    row 2: col=0에 Q 배치
      row 3: col=2에 Q 배치 → 해 발견!

N-Queen 해의 수

NN 해의 수 가지치기 효과
1 1 –
4 2 4!=244! = 24 → 2
8 92 8!=403208! = 40320 → 92
12 14,200 12!≈4.8×10812! \approx 4.8 \times 10^8 → 14,200
15 2,279,184 가지치기 없이는 사실상 불가능

복잡도 분석

  • 시간 복잡도: O(n!)O(n!) — 최악의 경우. 실제로는 가지치기로 훨씬 빠름
  • 공간 복잡도: O(n)O(n) — 재귀 스택 깊이 + 3개의 집합

조합의 합(Combination Sum) 문제

문제 정의

주어진 후보 숫자 배열 candidates에서 합이 target이 되는 모든 조합을 구한다. 같은 숫자를 무제한으로 사용할 수 있다.

Python 구현

def combination_sum(candidates, target):
    """합이 target이 되는 모든 조합을 구한다 (중복 사용 가능)"""
    result = []
    candidates.sort()  # 정렬하면 가지치기에 유리

    def backtrack(start, path, remaining):
        # 기저 조건: 목표 합에 도달
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            # 가지치기: 남은 값보다 큰 후보는 탐색 불필요
            if candidates[i] > remaining:
                break  # 정렬되어 있으므로 이후 값도 모두 초과

            path.append(candidates[i])
            # 같은 숫자 재사용 가능하므로 i (i+1이 아님)
            backtrack(i, path, remaining - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result


# 실행 예시
print(combination_sum([2, 3, 6, 7], 7))

출력:

[[2, 2, 3], [7]]

변형: 각 숫자를 한 번만 사용

def combination_sum2(candidates, target):
    """합이 target이 되는 조합 (각 숫자 1회만 사용, 중복 후보 허용)"""
    result = []
    candidates.sort()

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            # 같은 레벨에서 중복 값 건너뛰기
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])  # i+1: 재사용 불가
            path.pop()

    backtrack(0, [], target)
    return result


# 실행 예시
print(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8))

출력:

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

두 변형 비교

구분 Combination Sum I Combination Sum II
재사용 무제한 1회만
재귀 호출 시 backtrack(i, ...) backtrack(i + 1, ...)
중복 방지 불필요 (start로 해결) i > start and nums[i] == nums[i-1]
시간 복잡도 O(nt/m)O(n^{t/m}) O(2n)O(2^n)

여기서 tt는 target, mm은 candidates의 최솟값이다.

스도쿠 풀기 (고급)

문제 정의

9×99 \times 9 스도쿠 보드의 빈 칸을 채워서, 각 행·각 열·각 3×33 \times 3 박스에 1~9가 한 번씩만 나타나도록 한다.

Python 구현

def solve_sudoku(board):
    """스도쿠를 백트래킹으로 풀기"""

    # 각 행, 열, 박스에서 사용 중인 숫자를 집합으로 관리
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]  # 박스 인덱스: (row//3)*3 + col//3

    empty = []  # 빈 칸 좌표 목록

    # 초기 상태 설정
    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                num = int(board[r][c])
                rows[r].add(num)
                cols[c].add(num)
                boxes[(r // 3) * 3 + c // 3].add(num)
            else:
                empty.append((r, c))

    def backtrack(idx):
        # 기저 조건: 모든 빈 칸을 채웠음
        if idx == len(empty):
            return True

        r, c = empty[idx]
        box_id = (r // 3) * 3 + c // 3

        for num in range(1, 10):
            # 가지치기: 행, 열, 박스 충돌 검사
            if num in rows[r] or num in cols[c] or num in boxes[box_id]:
                continue

            # 숫자 배치
            board[r][c] = str(num)
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_id].add(num)

            if backtrack(idx + 1):  # 다음 빈 칸으로
                return True

            # 되돌림
            board[r][c] = '.'
            rows[r].remove(num)
            cols[c].remove(num)
            boxes[box_id].remove(num)

        return False  # 1~9 모두 불가능 → 백트래킹

    backtrack(0)
    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))

출력:

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

복잡도 분석

  • 시간 복잡도: O(9k)O(9^{k}) — kk는 빈 칸의 수. 실제로는 가지치기로 훨씬 빠름
  • 공간 복잡도: O(k)O(k) — 재귀 스택 깊이 (최대 81)

자주 하는 실수 & 엣지 케이스

1. 결과 저장 시 얕은 복사 실수

# 잘못된 코드: 모든 결과가 같은 리스트를 참조
result.append(path)       # path가 변경되면 result도 변경됨

# 올바른 코드: 깊은 복사로 현재 상태 저장
result.append(path[:])    # 슬라이싱으로 복사
result.append(list(path)) # 또는 list()로 복사

이것은 가장 흔한 실수다. path를 그대로 넣으면 이후 pop() 연산에 의해 이미 저장된 결과도 함께 변경된다.

2. 되돌림(backtrack) 누락

# 잘못된 코드: 상태 복원을 잊음
path.append(nums[i])
backtrack(path)
# path.pop() 누락!

# 올바른 코드
path.append(nums[i])
backtrack(path)
path.pop()  # 반드시 되돌려야 함

3. 중복 원소 처리 시 정렬 누락

중복 제거를 위한 nums[i] == nums[i-1] 조건은 배열이 정렬되어 있어야 동작한다. sort()를 빠뜨리면 중복이 제거되지 않는다.

4. 조합에서 start 인덱스 전달 실수

# 잘못된 코드: 순열이 생성됨
backtrack(0, path)         # 매번 처음부터 탐색

# 올바른 코드: 조합이 생성됨
backtrack(i + 1, path)     # 현재 이후부터 탐색

5. 가지치기 조건 순서

가지치기는 가능한 한 일찍 수행해야 효과적이다.

# 비효율적: 깊이 들어간 후 확인
path.append(nums[i])
if not is_valid(path):
    path.pop()
    continue
backtrack(path)
path.pop()

# 효율적: 선택 전에 확인
if not is_valid_choice(nums[i]):  # 선택 전 검증
    continue
path.append(nums[i])
backtrack(path)
path.pop()

백트래킹 문제 풀이 템플릿 정리

유형 기저 조건 반복 범위 재귀 인자 핵심 가지치기
순열 len(path) == n range(0, n) backtrack(path) used[i] 배열
조합 len(path) == r range(start, n) backtrack(i+1, path) start 인덱스
부분집합 없음 (매번 저장) range(start, n) backtrack(i+1, path) start 인덱스
N-Queen row == n range(0, n) backtrack(row+1) 열 + 대각선 집합
조합의 합 remaining == 0 range(start, n) backtrack(i, path) candidate > remaining
스도쿠 idx == len(empty) range(1, 10) backtrack(idx+1) 행·열·박스 집합

실전 응용 팁

비트마스킹으로 최적화

N-Queen과 같은 문제에서 집합 대신 비트마스크를 사용하면 상수 시간을 줄일 수 있다.

def n_queens_bitmask(n):
    """비트마스크를 활용한 N-Queen 카운팅"""
    count = 0

    def backtrack(row, cols, diag1, diag2):
        nonlocal count
        if row == n:
            count += 1
            return

        # 사용 가능한 열을 비트 연산으로 계산
        available = ((1 << n) - 1) & ~(cols | diag1 | diag2)

        while available:
            # 가장 오른쪽 1비트 추출
            pos = available & (-available)
            available ^= pos

            backtrack(
                row + 1,
                cols | pos,              # 열 마킹
                (diag1 | pos) << 1,      # 좌상→우하 대각선
                (diag2 | pos) >> 1       # 우상→좌하 대각선
            )

    backtrack(0, 0, 0, 0)
    return count


print(f"8-Queen 해의 수: {n_queens_bitmask(8)}")

출력:

8-Queen 해의 수: 92

itertools 활용 (코딩테스트 시간 절약)

Python 표준 라이브러리의 itertools로 기본적인 순열/조합을 빠르게 생성할 수 있다.

from itertools import permutations, combinations, product

# 순열
list(permutations([1, 2, 3], 2))    # [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]

# 조합
list(combinations([1, 2, 3, 4], 2)) # [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]

# 중복 순열 (데카르트 곱)
list(product([0, 1], repeat=3))     # 길이 3의 모든 이진 수열

단, itertools를 사용하면 가지치기가 불가능하다. 제약 조건이 복잡한 문제에서는 직접 백트래킹을 구현하는 것이 훨씬 효율적이다.

관련 변형 문제

문제 핵심 변형 포인트
괄호 생성 열린 괄호와 닫힌 괄호의 개수 제약
문자열 분할 (팰린드롬) 부분 문자열의 팰린드롬 검사가 가지치기
IP 주소 복원 각 세그먼트의 범위(0~255) 제약
단어 검색 (DFS) 2D 그리드 + 방문 여부
타겟 넘버 (+/-) 이진 선택 트리, BFS/DFS 모두 가능

마무리

백트래킹은 “체계적인 시행착오”라고 할 수 있다. 핵심을 정리하면 다음과 같다.

  1. 기본 구조를 암기하라: 선택 → 검증 → 진행/되돌림의 세 단계가 모든 백트래킹의 뼈대다
  2. 가지치기가 성능을 결정한다: 유망하지 않은 경로를 얼마나 빨리 걸러내느냐가 시간 복잡도를 좌우한다
  3. 순열/조합/부분집합의 차이를 명확히 구분하라: 반복 시작점(start vs 0)과 재사용 여부(i vs i+1)의 차이만 이해하면 대부분의 문제에 대응할 수 있다
  4. 되돌림을 절대 잊지 마라: append() 후에는 반드시 pop(), add() 후에는 반드시 remove()
  5. 결과 저장 시 반드시 복사하라: path[:] 또는 list(path) 사용
  6. 중복 처리는 정렬 + 인접 비교 패턴으로 해결한다

순열·조합 생성부터 시작해서 N-Queen, 조합의 합, 스도쿠까지 단계적으로 연습하면 백트래킹의 원리와 응용을 체계적으로 익힐 수 있다.

Related Posts

Coding InterviewTrie Data Structure for Fast String Search: Autocomplete and Prefix Matching in PythonBuild a trie from scratch in Python for autocomplete and prefix matching. Covers LeetCode 208, Word Search II, deletion gotchas, and benchmarks vs naive search.2026.01.12Coding Interview그리디 알고리즘 완벽 정리 – 활동 선택, 회의실 배정 등 코딩테스트 필수 유형 풀이그리디 알고리즘의 핵심 원리부터 활동 선택, 회의실 배정, 분할 가능 배낭, 동전 교환, 허프만 코딩까지 코딩테스트 필수 유형을 Python 코드와 단계별 시각화로 완벽 정리합니다. 난이도별 접근법과 자주 하는 실수까지 한 번에 정복하세요.2025.12.24Coding InterviewUnion-Find (Disjoint Set) from Basics to Kruskal’s Algorithm ImplementationLearn Union-Find from scratch: path compression, union by rank, and implementing Kruskal's MST. Real code, real mistakes, O(α(N)) performance.2026.01.31Coding Interview다이나믹 프로그래밍(DP) 패턴별 완전 정복 – Knapsack부터 비트마스킹 DP까지다이나믹 프로그래밍(DP)의 핵심 패턴을 완전 정복하세요. Knapsack, LIS, LCS부터 비트마스킹 DP까지 알고리즘 원리, Python 구현, 시간 복잡도 분석을 상세히 다룹니다.2025.12.25

Did you find this helpful?

☕ Buy me a coffee

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

TODAY 29 | TOTAL 2,726