Ch.9 재귀와 백트래킹

면접실전 — Combination Sum, N-Queens, Word Search

Combination Sum 문제의 중복 선택 허용 백트래킹을 구현한다N-Queens 문제를 통해 복잡한 가지치기 조건을 설계한다Word Search를 통해 2D 격자에서의 백트래킹을 익힌다

면접 단골 문제 5개를 한 번에 정복합니다

Subsets → Permutations → Combination Sum → N-Queens → Word Search. 난이도가 점점 올라가지만 모두 같은 백트래킹 템플릿의 변형입니다.

문제마다 조건이 다른데, 어떻게 같은 템플릿을 적용하지?

종료 조건, 선택지 범위, 가지치기 조건 — 이 세 가지만 바꾸면 됩니다.

article

핵심 내용

같은 원소를 여러 번 사용해도 되는 조합 문제입니다

문제: candidates = [2,3,6,7], target = 7 정답: 2,2,3], [7 같은 원소를 반복 선택 가능!

def combinationSum(candidates, target):
    result = []
    
    def backtrack(start, path, remaining):
        if remaining == 0:         # 합이 target이면 정답
            result.append(path[:])
            return
        if remaining < 0:          # 합이 초과하면 가지치기
            return
        
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i (not i+1)!
            path.pop()
    
    backtrack(0, [], target)
    return result

핵심: `backtrack(i, ...)` — i+1이 아닌 i부터 시작. 같은 원소를 다시 선택할 수 있습니다

n×n 체스판에 n개의 퀸을 서로 공격하지 않게 배치하라

퀸은 가로, 세로, 대각선 모두 공격 가능. 각 행에 하나씩 놓되, 열과 대각선이 겹치지 않아야 합니다

def solveNQueens(n):
    result = []
    cols = set()       # 사용 중인 열
    diag1 = set()      # 주대각선 (row - col)
    diag2 = set()      # 부대각선 (row + col)
    board = [['.' ] * n for _ in range(n)]
    
    def backtrack(row):
        if row == n:
            result.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)
            
            board[row][col] = '.'   # 되돌리기
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0)
    return result

가지치기 3가지: cols(열), diag1(\대각선), diag2(/대각선) 대각선 공식: 같은 주대각선 → row-col 같음, 같은 부대각선 → row+col 같음 set으로 O(1) 조회하여 효율적!

N-Queens는 면접 단골입니다. 가지치기 조건 3가지를 set으로 구현하는 것이 핵심

2D 격자에서 단어를 찾는 격자 백트래킹 문제입니다

board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']] word = 'ABCCED' → True 인접한 셀로 이동하며 단어를 완성

def exist(board, word):
    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 r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

board[r][c] = '#'로 방문 표시 → 재귀 후 원래 값 복원. visited 배열 대신 in-place 수정으로 공간 절약

면접에서 백트래킹 문제를 만나면 이 분류표로 판단합니다

부분집합(Subsets) — 모든 조합, start 인덱스 순열(Permutations) — 순서 중요, visited 배열 조합합(Combination Sum) — 합 조건, 중복 허용 시 start=i 격자탐색(Word Search) — 2D 이동, in-place 방문 배치(N-Queens) — 조건부 배치, set으로 충돌 검사

모두 같은 템플릿: 선택 → 탐색 → 되돌리기. 달라지는 것은 종료 조건, 선택 범위, 가지치기뿐

각 문제의 시간 복잡도를 정리합니다

Subsets: O(n × 2ⁿ) Permutations: O(n × n!) Combination Sum: O(n^(T/M)) (T=target, M=min candidate) N-Queens: O(n!) Word Search: O(m × n × 4^L) (L=word length)

백트래킹은 최악의 경우 지수적입니다. 하지만 가지치기로 실제 탐색은 훨씬 적습니다

Combination Sum에서 같은 원소를 반복 선택하려면 코드에서 어떻게 해야 하나?

N-Queens에서 같은 부대각선(/)을 판별하는 공식은?

Word Search에서 방문한 셀을 처리하는 효율적인 방법은?

image

시각 자료

다이어그램: ds-d73

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작