왜 필요한가 — 완전 탐색은 너무 크다

어떤 문제는 “가능한 모든 경우를 다 따져 보면” 답이 나온다. 예를 들어 8개의 퀸을 8×8 체스판에 서로 공격하지 못하게 놓는 문제는, 64개 칸 중 8개를 고르는 모든 조합을 하나하나 검사하면 언젠가는 답을 찾는다. 문제는 그 “모든 경우”의 개수다. 64개 칸에서 8개를 고르는 조합은 수천만 가지가 넘고, 순서까지 고려하면 훨씬 커진다. 이런 식의 완전 탐색(exhaustive search, 가능한 모든 경우를 빠짐없이 시도하는 탐색)은 문제 크기가 조금만 커져도 현실적인 시간 안에 끝나지 않는다.

백트래킹(backtracking, “되돌아가기”라는 뜻으로, 답이 될 수 없다고 판단되면 그 지점까지의 선택을 취소하고 이전 단계로 되돌아가는 탐색 기법)은 이 문제를 해결하는 접근이다. 해를 한 조각씩 만들어 가다가, 지금까지 만든 부분해가 “절대로 완전한 해가 될 수 없다”고 판단되는 순간 그 이후를 아예 만들어 보지 않고 되돌아간다. 이렇게 하면 완전 탐색과 달리 가망 없는 가지들을 통째로 잘라내므로(가지치기, pruning) 실제로 검사하는 경우의 수가 크게 줄어든다.

쉽게 말하면: 백트래킹은 “이 길로 가면 답이 안 나온다”는 게 확실해지는 순간 그 앞을 더 가 보지 않고 바로 되돌아 나오는 탐색이다.

백트래킹의 프레임워크 — 상태·유망성·해·부분해

백트래킹 문제는 대부분 다음 네 가지 요소로 정리할 수 있다.

• 상태(state): 지금까지의 선택으로 만들어진 부분적인 답. 예를 들어 N-Queen에서는 “1행에 퀸을 놓았고 2행에도 놓았다”까지의 상태.
• 부분해(partial solution): 아직 완성되지 않은, 만들어 가는 중인 해.
• 유망성 검사(promising check, 지금까지의 부분해가 완전한 해로 이어질 가능성이 있는지 확인하는 절차): 부분해가 이미 조건을 어겼다면(예: 두 퀸이 같은 열에 있다) 더 진행해도 소용없으므로 유망하지 않다고 판단한다.
• 해(solution): 모든 선택이 끝나 완전한 답이 만들어진 상태.

이 네 요소로 일반적인 백트래킹 의사코드를 쓰면 다음과 같다. 여기서 depth는 지금까지 몇 단계 선택했는지를 나타내는 깊이이고, n은 전체 선택해야 할 단계 수다.

procedure backtrack(depth):
    if depth == n:
        해 하나 완성됨 → 기록
        return
    for 후보 in depth번째 단계에서 고를 수 있는 모든 값:
        부분해에 후보를 추가
        if isPromising(부분해):     // 유망성 검사
            backtrack(depth + 1)     // 다음 단계로 전진
        부분해에서 후보를 제거        // 되돌아가기(backtrack)

이 틀에서 핵심은 isPromising 검사가 거짓이면 backtrack(depth + 1)을 아예 호출하지 않는다는 점이다. 즉 그 후보 아래에 있는 모든 하위 가지를 통째로 잘라낸다. 이것이 완전 탐색과 백트래킹의 근본적인 차이다.

예제 1 — 순열 생성으로 상태공간트리 이해하기

크기 3인 집합 {1, 2, 3}의 모든 순열을 만드는 문제로 상태공간트리(state space tree, 각 단계에서의 선택을 가지로 뻗어 나가며 만든 트리)를 직접 그려 보자. 순열이므로 유망성 검사는 “이미 사용한 숫자는 다시 고르지 않는다”이다.

이 트리에는 가지치기가 일어날 지점이 없다(어떤 숫자를 골라도 “이미 쓴 숫자만 아니면” 항상 유망하기 때문이다). 그래서 n개 원소의 순열을 모두 만드는 백트래킹은 결국 n!(n 팩토리얼)개의 잎 노드를 전부 만들어야 하고, 시간복잡도는 O(n!)이다. 이는 가지치기를 적용해도 줄어들지 않는, “해 자체의 개수가 원래 많은” 경우다.

자주 틀리는 점: 백트래킹을 쓴다고 해서 항상 지수 시간보다 빨라지는 것은 아니다. 순열 생성처럼 가능한 해의 개수 자체가 많은 문제는 백트래킹으로 풀어도 결국 그 개수만큼은 만들어야 한다. 백트래킹의 이득은 “유망하지 않은 가지를 미리 잘라 만들지 않는” 데서 나오며, 가지치기가 일어나지 않는 문제에서는 완전 탐색과 시간이 같다.

예제 2 — N-Queen 문제: 유망성 검사가 실제로 가지를 자르는 경우

N-Queen 문제는 N×N 체스판에 퀸 N개를 서로 공격하지 못하게(같은 행·열·대각선에 있지 않게) 배치하는 문제다. 4-Queen(N=4)으로 직접 추적해 보자. 퀸을 한 행에 하나씩만 놓는다고 가정하면, 상태는 “각 행에 퀸을 몇 번째 열에 놓았는가”의 목록이 된다.

유망성 검사는 새로 놓으려는 퀸이 이미 놓인 퀸들과 같은 열에 있는지, 같은 대각선에 있는지 확인한다. 두 퀸이 (row1, col1)과 (row2, col2)에 있을 때 같은 대각선에 있다는 조건은 다음과 같이 세운다.

이 값이 성립하면 두 퀸이 대각선으로 마주 보고 있어 서로 공격할 수 있으므로 유망하지 않다.

이 표에서 3행에서 “놓을 곳이 전혀 없어” 되돌아가는 순간이 바로 가지치기가 실제로 일어나는 지점이다. 1행 1열, 2행 3열까지 진행했을 때 3행에 퀸을 놓을 수 있는 열이 하나도 없다는 것을 확인하는 즉시, 4행까지 내려가 보지 않고 바로 2행으로 되돌아가 다른 열을 시도한다. 만약 백트래킹 없이 완전 탐색을 했다면 3행·4행에 아무 열이나 채워 넣은 뒤에야 “이건 답이 아니구나”를 알았을 것이다.

쉽게 말하면: 유망성 검사는 “이 수를 두는 순간 이미 진 게임인지” 매 수마다 확인하는 것이고, 가지치기는 그 확인 결과 진 게임이면 그 이후 수를 아예 두어 보지 않는 것이다.

예제 3 — 부분집합 탐색(부분합 문제)

집합 {3, 5, 6, 7}에서 합이 정확히 13이 되는 부분집합을 찾는 문제도 같은 틀로 풀 수 있다. 각 원소를 “포함한다/포함하지 않는다”의 두 갈래로 나누는 상태공간트리를 만들고, 유망성 검사로 “지금까지 고른 합이 이미 목표값을 넘었으면 더 진행하지 않는다”는 조건을 건다.

procedure subsetSum(depth, 현재합):
    if 현재합 == 13:
        해 발견 → 기록하고 return
    if depth == 4 or 현재합 > 13:
        return   // 유망하지 않음: 더 커지거나 원소가 없음
    subsetSum(depth+1, 현재합 + 원소[depth])   // 포함하는 경우
    subsetSum(depth+1, 현재합)                 // 포함하지 않는 경우

여기서 현재합 > 13이 되는 순간 그 가지 아래는 절대로 13을 만들 수 없으므로(원소가 모두 양수라는 전제에서) 바로 잘라낸다. 이런 식으로 “지금까지 쌓은 값이 목표를 넘었다”거나 “남은 원소를 다 더해도 목표에 못 미친다” 같은 조건은 부분합·배낭류 문제에서 아주 자주 쓰이는 유망성 검사다.

분기한정 — 백트래킹에 “최적값 추정”을 더하다

분기한정(branch and bound)은 백트래킹과 같은 상태공간트리 탐색 틀을 쓰지만, 목적이 다르다. 백트래킹은 “조건을 만족하는 해를 찾는” 문제(N-Queen, 부분집합 등)에 주로 쓰이고, 분기한정은 “여러 해 중 가장 좋은 값을 찾는” 최적화 문제(예: 배낭 문제에서 최대 가치)에 쓰인다.

분기한정은 각 가지에서 유망성 검사 대신 한계값(bound, 그 가지를 끝까지 파고들었을 때 얻을 수 있는 값의 상한 또는 하한 추정치)을 계산한다. 지금까지 찾은 최선의 해(현재까지의 최적값, incumbent)보다 그 가지의 한계값이 더 나쁘면, 실제로 끝까지 파 보지 않아도 “더 좋은 해가 나올 수 없다”는 것을 알 수 있으므로 가지를 잘라낸다.

0/1 배낭 문제(각 물건을 통째로 담거나 아예 담지 않는 배낭 문제, 무게 한도 W = 10)로 살펴보자. 물건이 (무게, 가치)로 A(4, 40), B(6, 60), C(5, 30) 세 개 있다고 하자. 각 물건의 가치 대비 무게 비율(무게당 가치)은 A: 10, B: 10, C: 6이다.

마지막 행이 분기한정의 핵심이다. “A를 담지 않는” 가지의 한계값(90)이 이미 찾아 놓은 최적값(100)보다 낮으므로, 그 가지 아래에서 어떤 조합을 만들어도 100을 넘을 수 없다는 것이 수학적으로 보장된다. 그래서 그 가지의 하위 경우들을 하나도 만들어 보지 않고 바로 잘라낼 수 있다.

쉽게 말하면: 백트래킹은 “이 길이 조건을 어겼는가”만 보고 자르고, 분기한정은 “이 길로 가 봤자 지금까지 찾은 최선보다 좋을 수 있는가”까지 계산해서 자른다.

백트래킹 vs 분기한정 비교

복잡도 — 최악은 여전히 지수 시간

백트래킹과 분기한정 모두 최악의 경우 시간복잡도는 여전히 지수 시간(O(2^n)이나 O(n!) 등)이다. 가지치기는 평균적으로, 또 실제 입력에서 탐색량을 극적으로 줄여 주지만, 이론적인 최악의 경우 보장을 다항 시간으로 바꿔 주지는 않는다. 예를 들어 N-Queen에서 애초에 답이 하나도 없는 배치라면(예: N=2, N=3), 백트래킹도 결국 모든 유망한 부분해를 다 시도해 본 뒤에야 “해가 없다”는 결론에 도달하므로 최악의 경우 시간은 완전 탐색과 크게 다르지 않을 수 있다.

자주 틀리는 점: “백트래킹을 쓰면 다항 시간에 풀린다”는 생각은 틀렸다. 백트래킹·분기한정은 평균적인 실제 탐색량을 줄이는 실용적 기법이지, 문제의 이론적 난이도(18편에서 다룰 P/NP 관점) 자체를 바꾸지는 않는다. N-Queen이나 배낭 문제 같은 조합 최적화 문제는 백트래킹으로 풀어도 최악의 경우 지수 시간이 걸릴 수 있다.

자주 틀리는 점

• 유망성 검사와 종료 조건을 혼동하는 실수: 유망성 검사는 “더 진행할 가치가 있는가”를 보는 것이고, 종료 조건(depth == n)은 “이미 완성됐는가”를 보는 것이다. 둘은 검사 시점과 목적이 다르다.
• 백트래킹이 항상 빠르다고 오해하는 실수: 가지치기가 거의 일어나지 않는 문제(순열 생성처럼)에서는 완전 탐색과 시간이 같다.
• 분기한정의 한계값을 최적값과 혼동하는 실수: 한계값은 “이 가지에서 나올 수 있는 최선의 가능성”이라는 추정치이지, 실제로 그 값이 나온다는 보장은 아니다.
• 백트래킹과 동적계획법(16편)을 혼동하는 실수: 동적계획법은 부분 문제의 결과를 저장해 재사용하지만, 백트래킹은 기본적으로 저장 없이 상태공간트리를 그대로 탐색한다. 다만 두 기법이 결합되는 문제도 있다.

핵심 정리

• 백트래킹은 상태·부분해·유망성 검사·해라는 네 요소로 이루어지며, 유망하지 않은 부분해 아래의 가지를 통째로 잘라낸다.
• 순열 생성처럼 해의 개수 자체가 많은 문제는 가지치기의 이득이 적어 여전히 O(n!) 수준이다.
• N-Queen의 유망성 검사는 같은 열·같은 대각선 여부(|row1-row2| = |col1-col2|)를 확인하는 것이다.
• 분기한정은 최적화 문제에서 한계값과 현재까지의 최적값을 비교해 가지를 잘라내며, 백트래킹의 참/거짓 유망성 검사보다 더 강한 수치 비교를 쓴다.
• 두 기법 모두 최악의 경우 시간복잡도는 지수 시간이며, 가지치기는 평균적인 실제 탐색량을 줄이는 실용적 기법이다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 학습정보  — 알고리즘 과목의 출제기준과 평가 수준 확인.
• Princeton Algorithms Course, Backtracking and Branch and Bound  — 백트래킹·분기한정의 상태공간트리 개념과 대표 예제 정리.