복잡도

백트래킹의 시간은 결국 방문한 노드 수 × 노드 하나에서 하는 일입니다. 최악의 경우 상태 공간 트리 전체를 돌기 때문에 대부분 지수 시간이나 계승 시간이 걸리고, 가지치기는 이 상한을 바꾸지 못하지만 실제로 도는 노드 수를 크게 줄입니다. 이 장에서는 대표 문제의 복잡도를 정리하고, 가지치기의 효과를 숫자로 확인한 뒤, 완전 탐색과 동적 계획법(DP)과 비교합니다.

대표 문제의 복잡도

시간에 붙은 n이나 k는 해 하나를 복사해 저장하는 비용입니다. 공간은 재귀 깊이와 path만 센 것이고, 결과 목록 자체는 해의 개수만큼 더 필요합니다. 최선의 경우는 문제에 따라 다릅니다. 해를 하나만 찾으면 되는 스도쿠는 첫 가지에서 바로 답이 나오면 빈 칸 수에 비례하는 시간에 끝나지만, 해를 모두 나열해야 하는 문제는 해의 개수 자체가 하한이 됩니다.

가지치기의 효과를 재 보기

N-Queens에서 실제로 방문한 노드 수를 세어, 가지치기 없이 행마다 아무 열이나 놓는 경우(n^n)와 열만 겹치지 않게 하는 경우(n!)와 비교합니다.

def count_nodes(n):
    cols, diag, anti = set(), set(), set()
    visited = 0

    def place(row):
        nonlocal visited
        visited += 1
        if row == n:
            return
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue
            cols.add(c); diag.add(row - c); anti.add(row + c)
            place(row + 1)
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)

    place(0)
    return visited

for n in (4, 8, 12):
    print(n, count_nodes(n))

n = 12에서 방문 노드는 n!의 0.2% 정도입니다. 상한은 같아도 실제 탐색량이 이만큼 달라지기 때문에 백트래킹이 쓸 만한 것입니다.

정렬과 한계값으로 더 자르기

합이 target이 되는 부분집합을 찾을 때 수를 미리 정렬해 두면, 어떤 수가 남은 합보다 크다는 순간 그 뒤의 수는 모두 볼 필요가 없습니다. continue가 아니라 break를 쓸 수 있다는 점이 중요합니다.

def subset_sum(nums, target):
    nums = sorted(nums)
    result, path = [], []

    def dfs(start, remain):
        if remain == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remain:
                break                 # 뒤의 수는 더 크므로 전부 잘라 냄
            path.append(nums[i])
            dfs(i + 1, remain - nums[i])
            path.pop()

    dfs(0, target)
    return result

print(subset_sum([8, 2, 6, 3, 5], 11))  # [[2, 3, 6], [3, 8], [5, 6]]

완전 탐색, DP와의 비교

같은 질문도 무엇을 묻느냐에 따라 답이 달라집니다. 합이 target인 부분집합을 모두 나열하라면 백트래킹이, 있는지만 묻거나 개수를 묻는다면 DP가 O(n · target)으로 훨씬 빠릅니다.

def count_subset_sum(nums, target):
    ways = [1] + [0] * target       # ways[s] = 합이 s인 부분집합 수
    for x in nums:
        for s in range(target, x - 1, -1):
            ways[s] += ways[s - x]
    return ways[target]

print(count_subset_sum([8, 2, 6, 3, 5], 11))  # 3

정리

• 백트래킹의 상한은 상태 공간 트리의 크기이며, 대개 2^n이나 n! 수준입니다.
• 가지치기는 상한을 바꾸지 않지만 실제 방문 노드를 몇 자릿수씩 줄입니다.
• 해를 모두 나열해야 하면 백트래킹, 개수나 최적값만 필요하고 하위 문제가 겹치면 DP를 먼저 검토합니다.