백트래킹 시간 초과 판단법, n 크기별 경우의 수 표와 가지치기 점검

완전 탐색 코드를 짜기 전에 "이게 시간 안에 끝날까"를 먼저 계산하지 않으면, 예제는 통과하고 큰 입력에서 시간 초과가 나요. 결론부터 말하면 파이썬 기준으로 순열은 n=9, 부분집합은 n=20 안팎이 1초 안에 끝나는 한계였어요. 그 위라면 가지치기로 버틸 수 있는지(가지가 일찍 잘리는 구조인지)를 따지고, 아니면 비트마스크 DP나 반으로 나누어 탐색하기로 바꾸는 게 맞아요.

이 글은 동작 원리 대신 고를 때 필요한 숫자만 다뤄요. 크기별 경우의 수, 실제 처리 시간, 가지치기를 어디에 어떻게 넣어야 효과가 나는지, 시간 초과·오답이 났을 때 확인 순서를 Apple M1·파이썬 3.14.8로 직접 재서 정리했어요(2026-10-27). 절대 시간은 기기마다 다르니 배수로 읽어 주세요.

백트래킹으로 될까, n 크기별 경우의 수 판단표

완전 탐색이 시간 안에 끝나는지는 잎(완성된 후보) 수 × 잎 하나 처리 비용으로 먼저 어림해요. 경우의 수는 파이썬 math 모듈 문서의 math.perm, math.comb 로 바로 계산할 수 있어요.

순열·부분집합 칸은 아래에서 직접 잰 값이고, 나머지는 "잎 100만 개 안팎"을 같은 기준으로 옮긴 어림이에요. 컴파일 언어는 이보다 여유가 있지만 언어·채점기마다 달라서, 경계 근처에서는 직접 재 보는 게 맞아요.

계산할 때 자주 빠뜨리는 게 중간 노드예요. 순열 트리는 잎이 n! 개지만 중간 노드까지 합치면 약 e·n! ≈ 2.7배예요. n=9에서 잎은 36만 2,880개인데 실제 재귀 호출은 98만 6,410번이었어요. 게다가 노드마다 for 루프가 n칸을 돌기 때문에, 순열은 실제 일이 n!·n 에 가까워요.

import math
print(math.factorial(10), math.comb(30, 15), 2 ** 25)
# 3628800 155117520 33554432

C(30, 15)가 1억 5,511만이라는 점은 자주 놓쳐요. "30개 중 절반 고르기"는 2³⁰의 15%나 되는 크기라, 조합이라고 작다고 보면 안 돼요.

직접 재 본 처리 시간, 재귀와 itertools·비트마스크

같은 일을 세 방식으로 만들고 세 번 중 가장 빠른 값을 적었어요(부분집합 비트마스크와 순열 n=11은 한 번). 결과를 저장하지 않고 개수만 셌어요.

여기서 읽을 점은 셋이에요.

1. 가지치기가 없으면 itertools 가 재귀보다 8~12배 빨라요. itertools 공식 문서의 permutations 는 C로 구현돼 있어서 파이썬 함수 호출 비용이 없어요. 조건 없이 전부 훑을 거라면 직접 짜지 말고 표준 라이브러리를 써요.
2. n이 하나 늘 때 순열은 약 10배, 부분집합은 2배 늘어요. n=9에서 0.77초면 n=10은 10초를 넘어요. "조금 느린데 최적화하면 되겠지"가 통하지 않는 영역이에요.
3. 비트마스크가 늘 빠른 건 아니에요. 마스크마다 [nums[i] for i in range(n) if mask >> i & 1] 로 목록을 다시 만들면 부분집합 하나에 O(n)이 들어서, 합을 한 칸씩 들고 내려가는 재귀(O(1))보다 6.7배 느렸어요. 비트마스크는 상태를 정수 하나로 저장하거나 DP 배열 인덱스로 쓸 때 이점이 커요. 비트 모양이 헷갈리면 진법 변환기로 마스크 값을 2진수로 풀어 확인해 보세요.

가지치기 효과, 목표값에 따라 뒤바뀌어요

가지치기는 "넣으면 무조건 빨라진다"가 아니에요. 어떤 조건으로 자르느냐가 입력 모양에 맞아야 효과가 나요. 1~100 사이 무작위 정수 22개에서 합이 목표값이 되는 부분집합을 모두 세는 문제로, 목표를 전체 합의 1/4·1/2·3/4로 바꿔 가며 다섯 번씩 평균을 냈어요.

• 없음: 모든 부분집합을 만들어요. 노드 2²² = 419만 4,304개.
• 초과만 검사: 지금까지 합이 목표를 넘으면 더 넣지 않아요.
• 초과 + 남은 합 검사: 오름차순 정렬한 뒤, 지금 합에 남은 원소를 전부 더해도 목표에 못 미치면 멈춰요.

목표가 작으면 "초과" 조건이 금방 걸려서 노드가 98% 줄어요(실행 3.2초 → 0.11초). 그런데 목표가 전체 합의 3/4이면 넘칠 일이 거의 없어서 2.4%밖에 안 줄고, 검사 비용 때문에 오히려 3.30초로 조금 더 느려졌어요. 이때 일을 한 건 반대쪽 조건이에요. "남은 걸 다 더해도 모자람"을 넣자 32만 9천 개(92% 감소, 0.43초)로 떨어졌어요.

정리하면 가지치기는 양쪽 경계를 다 넣어야 입력이 어느 쪽으로 치우쳐도 버텨요. 위키백과 분기 한정법(Branch and bound) 항목이 설명하는 상한·하한 비교가 같은 생각이고, 최적화 문제라면 "지금까지 찾은 최선보다 나아질 수 없으면 중단"이 세 번째 경계가 돼요.

정렬 후 break 는 노드보다 루프를 줄여요

오름차순 정렬을 해 두면 s + a[i] > T 인 순간 뒤쪽 원소도 전부 넘치니 continue 대신 break 로 루프를 끝낼 수 있어요. 실험에서 방문 노드 수는 같았고, 목표 1/4일 때 시간만 0.107초에서 0.095초로 약 11% 줄었어요. 노드를 줄이는 건 경계 조건이고, break 는 노드 안의 헛도는 루프를 줄이는 장치예요.

중복 원소는 만들기 전에 건너뛰어요

[1,1,1,1,2,2,2,2] 의 서로 다른 순열은 70개뿐인데 itertools.permutations 는 위치로 구분해서 4만 320개를 만들어요. set() 으로 거르면 0.0117초, 정렬한 뒤 "같은 값의 앞 원소를 안 썼으면 건너뛰기" 한 줄을 넣은 재귀는 노드 251개에 0.0004초였어요.

def unique_perms(nums):
    nums = sorted(nums)
    used, path, out = [False] * len(nums), [], []
    def go():
        if len(path) == len(nums):
            out.append(tuple(path)); return
        for i, v in enumerate(nums):
            if used[i] or (i and v == nums[i - 1] and not used[i - 1]):
                continue
            used[i] = True; path.append(v)
            go()
            path.pop(); used[i] = False
    go(); return out

N-Queen 으로 본 구현별 차이, 비트마스크와 대칭

가지치기를 넣은 뒤에도 같은 트리를 얼마나 싸게 도느냐에서 몇 배가 갈려요. 같은 가지치기 규칙으로 세 가지 구현을 n=10~13에서 한 번씩 쟀어요. 해의 개수는 모두 OEIS A000170 값(724, 2,680, 14,200, 73,712)과 같았어요.

• 비트마스크: 놓을 수 있는 열을 full & ~(cols | 왼대각 | 오른대각) 한 번으로 구하고, avail & -avail 로 가장 낮은 비트부터 꺼내요. 막힌 열을 루프에서 하나씩 건너뛰지 않으니 1.4~2배 빨라졌고, n이 클수록 차이가 커졌어요.
• 좌우 대칭: 첫 줄의 퀸을 왼쪽 절반에만 두고 센 값을 2배 해요(n이 홀수면 가운데 열은 따로 한 번). 일이 절반이라 다시 1.8~2배 빨라졌어요.

n이 하나 늘 때마다 시간이 약 5~6배 늘어요. 그래서 구현을 4배 빠르게 다듬어도 버틸 수 있는 n은 하나 늘어날 뿐이에요. 구현 최적화는 경계에 걸린 n을 한 칸 넘기는 용도이고, 두 칸 이상 모자라면 방법을 바꿔야 해요.

백트래킹 대신 무엇을 쓰나, 비트마스크 DP와 반으로 나누기

입력이 표의 한계를 크게 넘으면 가지치기로는 안 돼요. 대표적인 두 가지 전환이 있어요.

외판원 문제(모든 도시를 한 번씩 도는 최단 경로): 16개 도시를 순열로 풀면 출발점을 고정해도 15! = 1조 3,077억 개예요. 위키백과 Held–Karp 알고리즘 항목대로 "방문한 도시 집합 + 마지막 도시"를 상태로 두는 DP는 Θ(2ⁿ·n²)이라 2¹⁶ × 16² = 1,677만 7,216 단위예요. 경로 순서가 아니라 집합만 같으면 이후가 같다는 점이 보이면 DP로 바꿀 수 있어요. 대신 메모리가 2ⁿ·n 칸 필요해서 n=20이면 2,097만 칸이에요.

부분집합 합 n=40: 2⁴⁰ = 1조 995억이라 그대로는 불가능해요. 위키백과 부분집합 합 문제 항목의 Horowitz–Sahni 방식처럼 원소를 20개씩 나눠 각각 2²⁰ = 104만 8,576개의 합을 만들고, 한쪽을 정렬한 뒤 이분 탐색으로 짝을 찾아요. 파이썬으로 답이 없는 최악의 경우 4.2초가 걸렸어요(원소 10⁹ 이하 무작위). 시간 제한이 빡빡하면 C++ 이나 정렬 두 개를 투 포인터로 맞추는 방식으로 줄여요. 이 방식은 2²⁰개 합을 다 들고 있어야 해서 메모리가 시간보다 먼저 문제가 될 수 있어요.

운영에서 자주 나는 문제와 확인 순서, 체크리스트

코딩 테스트뿐 아니라 테스트 케이스 조합 생성, 설정값 조합 탐색, 배정·스케줄 검증 같은 서비스 코드에도 완전 탐색이 들어가요. 문제가 났을 때는 아래 순서로 보면 대부분 위쪽에서 걸려요.

1. 최악 입력의 트리 크기: 예제가 아니라 제약 최댓값으로 잎 개수를 계산해요. 위 표를 넘으면 코드를 다듬기 전에 방법부터 바꿔요.
2. 가지치기 위치와 경계: 재귀 첫 줄에서 return 하지 말고 자식을 부르기 전 루프 안에서 걸러요. 한쪽 경계만 넣었다면 반대쪽 경계도 넣어요.
3. 중복 원소: 입력에 같은 값이 있는데 결과가 "서로 다른" 것만 필요하면 정렬 + 건너뛰기를 넣어요. 결과를 set 으로 거르고 있으면 그 자리가 병목이에요.
4. 결과 저장과 메모리: list(permutations(range(9))) 는 36만 개에 약 46.5MB를 썼어요(tracemalloc 측정). 개당 약 128바이트라 n=10이면 약 465MB, n=11이면 5GB를 넘어요(같은 비율로 계산). 다 모을 필요가 없으면 제너레이터(yield)로 하나씩 넘겨요.
5. 재귀 깊이: 파이썬 기본 한도는 sys.getrecursionlimit() 으로 1,000이에요. 백트래킹은 깊이가 보통 n 이라 문제가 적지만, 문자열을 앞에서부터 한 글자씩 잘라 사전 단어로 나누는 탐색처럼 깊이가 입력 길이와 같은 재귀에 길이 2,000짜리 문자열이 들어오면 걸려요. sys 모듈 공식 문서는 한도를 너무 높이면 인터프리터가 죽을 수 있다고 경고하니, 깊이가 큰 경우는 반복문과 명시적 스택으로 바꾸는 편이 안전해요.

고친 뒤엔 n이 8 이하인 무작위 입력 수백 개로 가지치기 없는 버전과 답을 대조해요. 가지치기 버그는 "해를 조금 덜 찾는" 모양으로 나와서 예외가 없거든요. 같은 대조 방식은 그리디 반례 찾기 체크리스트에도 정리해 뒀어요.

서비스 코드라면 예산을 걸어요

입력 크기를 서비스가 통제하지 못하면 최악의 경우 요청 하나가 몇 분씩 CPU를 잡아요. 방문 노드 수에 상한(예: 100만)을 두고 넘으면 "부분 결과 + 탐색 중단" 상태를 돌려주게 만들면, 타임아웃보다 원인 파악이 쉬워요.

도입 전에 따질 것

• 출력 자체가 지수 크기인가: "모든 순열을 출력하라"면 가지치기로 줄일 게 없어요. 출력 개수 자체가 시간 하한이에요.
• 물어보는 게 개수·최솟값뿐인가: 그렇다면 하나씩 만들지 않고 세는 DP가 있는지 먼저 봐요. 상태를 "어떤 걸 썼나" 집합으로 줄일 수 있으면 비트마스크 DP 후보예요.
• 가지가 일찍 잘리는 구조인가: N-Queen·스도쿠처럼 앞에서 충돌이 바로 드러나는 문제는 가지치기가 잘 먹혀요. 끝까지 가야 조건을 판단할 수 있는 문제는 가지치기 효과가 거의 없어요.
• 최악 입력이 실제로 들어오나: 부분집합 합 실험처럼 입력 분포에 따라 10배 넘게 차이 나요. 평균이 아니라 가장 불리한 목표값으로 재 봐요.

탐색 순서 자체를 고르는 기준은 BFS DFS 판단표에 따로 정리해 뒀어요.

자주 묻는 질문

n이 몇이면 백트래킹으로 풀어도 되나요?

파이썬 1초 기준으로 순열은 n ≤ 9, 부분집합은 n ≤ 20이 직접 잰 한계였어요. 잎 개수가 100만 안팎을 넘으면 가지치기가 일찍 잘리는 구조인지 따져 보고, 아니면 비트마스크 DP나 반으로 나누기로 바꿔요.

itertools 를 쓰면 되는데 백트래킹을 직접 짜야 하나요?

조건 없이 전부 훑는다면 itertools 가 8~12배 빨라요. 다만 itertools 는 완성된 결과만 내기 때문에 중간에 가지를 칠 수 없어요. 앞부분만 보고 버릴 수 있는 조건이 있으면 직접 짠 재귀가 노드를 수십 배 줄여서 결국 더 빨라요.

가지치기를 넣었는데 오히려 느려졌어요.

조건이 거의 걸리지 않는 입력이면 검사 비용만 더해져요. 부분집합 합에서 목표가 전체 합의 3/4일 때 "초과" 검사만 넣으면 노드가 2.4%밖에 안 줄고 시간은 조금 늘었어요. 반대 방향 경계("남은 걸 다 더해도 모자람")를 같이 넣으면 92%가 줄었어요.

비트마스크가 재귀보다 항상 빠른가요?

아니에요. 마스크마다 원소 목록을 다시 만들면 부분집합 하나에 O(n)이 들어 재귀보다 6.7배 느렸어요. 비트마스크는 N-Queen 의 놓을 수 있는 열 계산이나 DP 상태 저장처럼 정수 연산 한 번으로 집합을 다룰 때 빨라져요.

RecursionError 가 나면 한도를 올리면 되나요?

깊이가 수천 정도면 sys.setrecursionlimit 으로 버틸 수 있지만, 공식 문서는 너무 높이면 인터프리터가 죽을 수 있다고 경고해요. 백트래킹에서 깊이가 그만큼 깊다면 트리 크기가 이미 감당할 수 없는 경우가 많으니, 방법부터 다시 보는 게 먼저예요.

모든 조합을 리스트에 담았더니 메모리가 부족해요.

순열 9개 전부를 리스트로 담으면 약 46.5MB였고, 한 개 늘 때마다 약 10배씩 늘어요. 하나씩 처리하고 버리도록 제너레이터로 바꾸거나, 정말 필요한 건 개수·최선값뿐인지 다시 확인해요.

정리

• 시작 전에 최악 입력의 잎 개수를 계산해요. 파이썬 1초 기준 순열 n ≤ 9, 부분집합 n ≤ 20이 직접 잰 한계였어요.
• 가지치기는 양쪽 경계(넘침·모자람)를 다 넣어야 입력이 어느 쪽으로 치우쳐도 버텨요. 한쪽만 넣으면 목표값에 따라 효과가 98%에서 2%까지 떨어졌어요.
• 비트마스크·대칭 같은 구현 최적화는 몇 배를 벌어 주지만 n 한 칸 정도예요. 더 모자라면 비트마스크 DP나 반으로 나누기로 바꿔요.
• 시간 초과·오답이 나면 트리 크기 → 가지치기 위치 → 중복 → 결과 저장 → 재귀 깊이 순서로 보고, 작은 입력에서 가지치기 없는 버전과 대조해요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 백트래킹 원리 — 순열·조합·부분집합 완전 탐색과 가지치기에서 도식과 코드로 단계별로 풀었어요.