E-1: 재귀와 완전탐색 — 지름길이 없으면 다 뒤진다

안녕하세요, 여러분의 알고리즘 길잡이 홍순구 튜터입니다. 지난 시간까지 우리는 카테고리 D를 마치며 정렬을 발판 삼아 "영리하게 훑어" 문제를 O(n)·O(log n)으로 눌렀습니다. 이진 탐색은 절반씩 버렸고, 투 포인터는 양 끝에서 조여 왔고, 슬라이딩 윈도우는 창문을 미끄러뜨렸죠. 다들 "이중 반복문 O(n²)를 어떻게든 눌러 내리는" 영리한 지름길이었습니다.

그런데 세상엔 그런 지름길이 아예 없는 문제가 있어요. "가능한 모든 경우를 하나도 빠짐없이 다 만들어 봐야만" 답이 나오는 문제들입니다. 지난 시간 마지막에 제가 이런 예고를 했었죠. "영리한 지름길이 없어 모든 경우를 다 뒤져야만 하는 문제로 들어간다"고요. 오늘이 바로 그 완전탐색입니다.

완전탐색의 뼈대는 자기 자신을 부르는 재귀(recursion)예요. 그리고 다 뒤지되 가망 없는 가지는 미리 쳐 내는 백트래킹(backtracking)까지 나아갑니다. 오늘부터 카테고리 E(알고리즘 패러다임)에 들어서는데, "문제를 푸는 다섯 가지 사고법" 중 첫 번째가 완전탐색이에요. 지난 시간이 O(n)의 우아함이었다면, 오늘은 O(2ⁿ)·O(n!)이라는 폭발하는 세계와, 그걸 다루는 법을 만납니다.

 오늘의 여정 — 재귀로 다 뒤지고, 백트래킹으로 헛일을 줄인다

   재귀            함수가 자기 자신을 부른다
     │  ├─ 종료 조건 (base case)         더 안 파고들고 되돌아간다
     │  └─ 자기 호출 (점화)              호출 스택에 쌓였다 풀린다(unwind)
     ▼
   완전탐색        모든 경우를 다 만들어 확인한다
     │  ├─ 부분집합 (넣기/빼기)          2ⁿ개
     │  ├─ 순열 (순서 있음)              n!개
     │  └─ 조합 (순서 없음)              nCr개
     ▼
   백트래킹        가망 없는 가지를 미리 접는다(가지치기)
        ├─ 부분집합 합                   넘어서면 그 아래로 안 내려간다
        └─ N-Queen                      같은 열·대각선이면 즉시 되돌아간다

💡 오늘 수업의 핵심 — "종료 조건으로 재귀를 세우고, 완전탐색으로 다 뒤지되, 백트래킹으로 헛일을 줄인다"

🎯 학습 목표

• 종료 조건(base case)과 자기 호출로 재귀를 설계하고, 호출 스택이 쌓였다 거꾸로 풀리는 과정을 눈으로 따라간다.
• 완전탐색으로 모든 경우(부분집합·순열·조합)를 빠짐없이 만들고, 그 경우의 수를 빅오(2ⁿ·n!)로 가늠한다.
• 백트래킹으로 가망 없는 가지를 미리 쳐 내 완전탐색의 헛일을 줄인다 — 부분집합의 합과 N-Queen으로 굳힌다.

Step 1: "함수가 자기를 부른다" (재귀의 두 기둥)

재귀(recursion)는 함수가 자기 자신을 호출하는 겁니다. 말로만 들으면 "함수가 자기를 부르면 무한히 도는 거 아닌가?" 싶은데, 그렇지 않게 막아 주는 장치가 있어요. 재귀는 언제나 두 기둥으로 섭니다.

• 종료 조건(base case) — 더 파고들지 않고 곧장 답을 돌려주는 가장 작은 경우.
• 재귀 호출(점화) — 큰 문제를 한 단계 작은 문제로 미루는 자기 호출.

가장 유명한 예제인 팩토리얼로 잡아 봅시다. n! = n × (n-1) × … × 1 이고, 0! = 1 입니다. 이걸 "n! = n × (n-1)!" 이라는 점화식으로 보면, 큰 문제(n!)가 한 단계 작은 문제((n-1)!)로 미뤄져요. 그리고 n이 0이나 1까지 작아지면 더 미룰 것 없이 1을 돌려주면 됩니다. 이게 종료 조건이에요.

# algorithms/backtracking.py
def factorial(n):
    if n <= 1:              # 종료 조건: 더 파고들지 않고 되돌아간다
        return 1
    return n * factorial(n - 1)

딱 세 줄인데 이 안에 재귀의 전부가 들어 있습니다. 첫 두 줄이 종료 조건, 마지막 줄이 자기 호출이에요. factorial(n)을 풀려고 factorial(n - 1)을 부르고, 그건 다시 factorial(n - 2)를 부르고… 이렇게 미루다 보면 결국 factorial(1)에 닿아 1을 돌려주고, 그때부터 거꾸로 곱셈이 채워집니다.

호출 스택 — 쌓였다가 거꾸로 풀린다

"거꾸로 곱셈이 채워진다"는 게 핵심입니다. 함수를 부르면 그 호출이 호출 스택(call stack)에 쌓여요. 스택은 B-1에서 배운 그 후입선출(LIFO) 자료구조 맞습니다. 나중에 부른 게 먼저 끝나죠. factorial(4)가 어떻게 쌓였다 풀리는지 그려 보겠습니다.

   factorial(4)  호출
   │  return 4 * factorial(3)   ← factorial(3)의 답을 기다리며 스택에 쌓인다
   │     factorial(3)
   │     │  return 3 * factorial(2)
   │     │     factorial(2)
   │     │     │  return 2 * factorial(1)
   │     │     │     factorial(1)
   │     │     │     └ return 1  ← 종료 조건(base case): 더 안 쌓고 되돌아간다
   │     │     └ 2 * 1 = 2       ┐
   │     └ 3 * 2 = 6             │ 스택을 거꾸로 풀며(unwind)
   └ 4 * 6 = 24                  ┘ 답이 위로 전달된다

위에서 아래로 내려가는 게 "쌓이는" 과정입니다. factorial(4)는 factorial(3)의 답을 받아야 곱셈을 끝낼 수 있으니, 답을 기다리며 스택에 남아 있어요. 그렇게 종료 조건(factorial(1) = 1)에 닿으면, 이제 아래에서 위로 거꾸로 풀립니다(unwind). 1을 받은 factorial(2)가 2를 돌려주고, 그걸 받은 factorial(3)이 6을, 마지막으로 factorial(4)가 24를 돌려줍니다.

이 "쌓였다 거꾸로 풀리는" 그림이 오늘 배울 모든 것의 바탕입니다. 완전탐색도, 백트래킹도, 다음에 배울 DFS도, 전부 이 호출 스택 위에서 돌아요. 그래서 이 그림 하나를 손에 익히면 카테고리 E 전체가 수월해집니다.

빅오를 달아 볼까요. factorial(n)은 호출이 n번 일어나니 시간이 O(n)입니다. 그런데 공간도 봐야 해요. 호출이 스택에 최대 n칸까지 쌓이니 공간이 O(n)입니다. 반복문으로 팩토리얼을 짜면 공간이 O(1)인데, 재귀는 호출 스택만큼 공간을 더 씁니다. 이 차이가 다음 Step의 주제예요.

⚠️ 종료 조건을 빼먹으면 재귀는 영원히 자기를 부르다 스택이 꽉 차 터집니다. 재귀를 짤 때 가장 먼저 "가장 작은 경우, 언제 멈추지?"부터 정하세요. 그게 첫 줄에 와야 합니다.

💡 한 줄 정리

재귀는 두 기둥으로 선다. 종료 조건(base case)에서 멈추고, 자기 호출로 큰 문제를 한 단계 작은 문제로 미룬다. 호출이 스택에 쌓였다가 종료 조건에서 거꾸로 풀리며(unwind) 답이 위로 전달된다.

Step 2: "호출 스택엔 바닥이 있다" (재귀 깊이·재귀 vs 반복)

재귀가 호출 스택을 쓴다는 걸 봤으니, 자연스러운 질문이 따라옵니다. "그럼 스택은 무한히 쌓을 수 있나요?" 아니요. 호출 스택엔 바닥이 있습니다. Python은 기본적으로 재귀 깊이를 약 1000으로 제한해요. 이보다 깊이 들어가면 RecursionError가 납니다. factorial(2000) 같은 걸 순진하게 재귀로 부르면 답이 아니라 에러를 만나요.

코딩테스트에서 트리나 그래프가 깊을 때, 혹은 재귀로 1부터 10만까지 더할 때 이 벽에 자주 부딪힙니다. 그래서 Python으로 깊은 재귀를 쓸 땐 맨 위에 이 한 줄을 답니다.

import sys
sys.setrecursionlimit(10**6)     # 재귀 깊이 한도를 100만으로 늘린다(코테 상투구)

이건 코딩테스트에서 거의 상투적으로 적어 두는 주문이에요. 다만 한도를 늘린다고 스택이 무한이 되는 건 아닙니다. 실제 메모리 한계는 여전히 있어서, 너무 깊으면 프로그램 자체가 죽을 수 있어요. 그래서 "재귀 깊이가 감당 안 될 만큼 깊어질 것 같으면, 아예 반복문으로 바꾼다"는 선택지를 늘 함께 쥐고 있어야 합니다.

같은 계산, 반복으로

팩토리얼을 반복문으로 짜면 이렇게 됩니다. 호출 스택을 전혀 쓰지 않죠.

def factorial_iter(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

값은 재귀 버전과 완전히 같습니다. 다만 뼈대가 달라요. 반복은 호출 스택을 쓰지 않으니 깊이 한계에 걸리지 않고, 공간이 O(1)입니다(재귀는 O(n)이었죠). 그럼 늘 반복이 나은가? 그렇지도 않습니다. 트레이드오프를 정리해 봅시다.

 재귀 vs 반복 — 같은 계산, 다른 뼈대

              재귀                        반복
   공간       O(n) 호출 스택              O(1) 변수 몇 개
   깊이       기본 약 1000 제한           제한 없음
   가독성     점화식 그대로라 읽기 쉽다    구조가 복잡하면 코드가 꼬인다
   잘 맞는 곳  트리·그래프·분할정복처럼    단순 누적·순차 계산
              문제 자체가 재귀적일 때

팩토리얼처럼 단순한 누적은 반복이 깔끔합니다. 하지만 트리를 타고 내려가거나(C-1 순회), 그래프를 뒤지거나(다음 시간 DFS), 문제를 반씩 쪼개는(E-3 분할정복) 상황은 문제의 구조 자체가 재귀적이라, 재귀로 쓰면 점화식이 코드에 그대로 드러나 훨씬 읽기 쉬워요. "모든 재귀는 반복으로 바꿀 수 있다"는 건 이론적으로 맞지만, 억지로 바꾸면 직접 스택을 들고 다니느라 코드가 더 복잡해지기도 합니다. 그래서 판단 기준은 이거예요. 깊이가 위험할 만큼 깊지 않고 구조가 재귀적이면 재귀로, 깊이가 감당 안 되거나 계산이 단순 순차면 반복으로.

💡 한 줄 정리

재귀는 호출 스택을 써서 깊이 한계(약 1000)와 O(n) 공간이 따르고, 반복은 스택 없이 O(1)이다. 구조가 재귀적이면 재귀로, 깊이가 위험하거나 계산이 단순 순차면 반복으로 고른다.

Step 3: "지름길이 없으면 다 뒤진다" (완전탐색)

이제 오늘의 본론입니다. 지난 시간 우리는 "이중 반복문 O(n²)를 O(n)으로 누르는" 영리한 방법들을 배웠어요. 그런데 그런 지름길이 없는 문제는 어떻게 풀까요? 답은 단순합니다. 가능한 모든 경우를 하나도 빠짐없이 다 만들어 보고, 그중에서 답을 고른다. 이걸 완전탐색(브루트포스, brute force)이라고 불러요. "무식하게 다 해 본다"는 뜻입니다.

무식해 보여도 완전탐색은 강력합니다. 모든 경우를 다 보니 답을 놓칠 수가 없어요. 그리고 조건만 정확히 옮기면 논리가 틀릴 일이 적습니다. 코딩테스트에서 "n이 작다"는 신호가 보이면(예: n ≤ 20), 출제자가 "영리한 지름길 대신 다 뒤져도 된다"고 허락한 셈이에요.

대표 예제로 부분집합을 다 만들어 봅시다. 원소가 있는 집합에서 뽑을 수 있는 모든 부분집합(멱집합)을 만드는 거예요. 핵심 착상은 이겁니다. 각 원소는 "넣거나" "빼거나" 둘 중 하나다. 원소를 하나씩 보면서 이 두 갈래로 갈라져 내려가면, 모든 조합이 빠짐없이 나옵니다.

# algorithms/backtracking.py
def all_subsets(items):
    result = []
    n = len(items)

    def choose(i, current):
        if i == n:                  # 종료 조건: n개를 모두 결정했다
            result.append(current[:])
            return
        current.append(items[i])    # 가지 1: items[i]를 넣는다
        choose(i + 1, current)
        current.pop()               # 가지 2: items[i]를 뺀다(되돌리고 진행)
        choose(i + 1, current)

    choose(0, [])
    return result

choose(i, current)는 "지금 i번 원소를 결정할 차례이고, 여기까지 고른 게 current다"라는 뜻입니다. i가 n에 닿으면 모든 원소를 다 결정했으니(종료 조건), 그때의 current를 하나의 부분집합으로 담아요. current[:]로 복사해 담는 게 중요한데, current는 계속 바뀌니 그 순간의 스냅샷을 떠 두는 겁니다. 그 아래는 두 갈래예요. items[i]를 넣고 내려간 뒤, 다시 빼고(pop) 내려갑니다. 이 그림을 그려 보죠.

 부분집합 완전탐색 — 각 원소마다 '넣기 / 빼기' 두 갈래 (items = [1, 2])

 choose(0, [])                     원소 1을 결정
 ├─ 넣기 → choose(1, [1])          원소 2를 결정
 │   ├─ 넣기 → [1, 2]   (잎)
 │   └─ 빼기 → [1]      (잎)
 └─ 빼기 → choose(1, [])
     ├─ 넣기 → [2]      (잎)
     └─ 빼기 → []       (잎)

 원소 2개 → 갈래 2² = 4개 잎 = 부분집합 4개. 원소 n개면 2ⁿ개.

원소마다 2갈래로 갈라지니, 원소가 n개면 잎이 2ⁿ개입니다. 그래서 부분집합이 2ⁿ개예요. 시간도 공간도 O(2ⁿ)입니다. 여기서 완전탐색의 결정적 약점이 보입니다. 경우의 수가 폭발해요.

"1초 1억" 잣대로 본 완전탐색의 한계

이 과목의 잣대, "1초에 약 1억 번 연산"을 대 봅시다. 완전탐색은 n이 조금만 커져도 감당이 안 됩니다.

   n       2ⁿ (부분집합)       n! (순열)
   10      약 1,000           약 360만
   13      약 8,000           약 62억          ← n!이 시간 초과로 접어든다
   20      약 100만           약 2.4 × 10¹⁸    ← n!은 천문학적
   30      약 10억            —                ← 2ⁿ마저 한계에 닿는다

부분집합(2ⁿ)은 n이 20~25 근처, 순열(n!)은 n이 10 근처가 한계입니다. 그래서 완전탐색을 떠올릴 땐 늘 입력 크기를 먼저 봐요. n이 작으면(20 이하쯤) 완전탐색이 가장 정직하고 안전한 답입니다. n이 크면 완전탐색은 시간 초과라, 가지치기(다음다음 Step 백트래킹)나 동적 계획법(E-4)으로 넘어가야 해요. "n을 보고 완전탐색이 되는지 먼저 가늠한다" — 이게 코딩테스트의 첫 판단입니다.

💡 한 줄 정리

완전탐색은 모든 경우를 다 만들어 확인한다. 부분집합은 각 원소를 넣거나 빼서 2ⁿ개다. 경우의 수가 폭발하니 "n이 작다"(20 안팎)가 완전탐색의 전제다.

Step 4: "순서가 있는 나열" (순열)

부분집합이 "넣거나 빼거나"였다면, 이번엔 뽑은 원소를 순서까지 따져 나열하는 순열(permutation)입니다. [1, 2]와 [2, 1]을 서로 다른 것으로 세요. 예를 들어 세 사람을 일렬로 세우는 경우의 수가 순열입니다. 코딩테스트의 "N과 M" 유형이 바로 이 골격이에요 — 1부터 N까지 중 M개를 순서 있게 고르는 문제죠.

핵심은 "아직 안 쓴 원소"를 골라 하나씩 자리를 채우는 겁니다. 이미 쓴 원소를 또 쓰면 안 되니, used라는 체크 배열로 표시해 둬요.

# algorithms/backtracking.py
def permutations(items, r=None):
    n = len(items)
    if r is None:
        r = n
    result = []
    used = [False] * n
    current = []

    def backtrack():
        if len(current) == r:       # 종료 조건: r개를 다 골랐다
            result.append(current[:])
            return
        for i in range(n):
            if used[i]:             # 이미 쓴 원소는 건너뛴다
                continue
            used[i] = True
            current.append(items[i])
            backtrack()
            current.pop()           # 되돌리기(백트래킹)
            used[i] = False

    backtrack()
    return result

current에 r개가 차면 하나의 순열로 담습니다. 아직 덜 찼으면, 안 쓴 원소를 하나 골라 used에 표시하고 내려간 뒤, 돌아와서 표시를 되돌려요(used[i] = False). 이 "골랐다가 되돌리는" 움직임이 오늘 계속 나오는 백트래킹의 기본 동작입니다. 되돌려 놔야 다음 반복에서 그 원소를 다른 자리에 쓸 수 있거든요.

 순열 permutations([1, 2, 3]) — 안 쓴 원소를 골라 자리를 채운다

 첫째 = 1 ─ 둘째 = 2 ─ 셋째 = 3 → [1, 2, 3]
        │        └ 셋째 = 3 없으면 2 → ...
        ├ 둘째 = 2 → 셋째 = 3 → [1, 2, 3]
        │           셋째 = ... 
 (전체) [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] — 3! = 6개

전체 순열은 n!개라, 시간이 O(n! × n)입니다(각 순열을 담는 데 n). Step 3 표에서 봤듯 n!은 폭발이 빨라, n이 10만 넘어도 위험해요. 그래서 순열 완전탐색은 n이 아주 작을 때만 씁니다.

두 트랙 — 직접 구현했으니, 실전에선 내장을 쓴다

원리를 봤으니 실전 이야기를 하죠. 코딩테스트에서 순열이 필요하면 위처럼 직접 짜지 않고 itertools.permutations를 씁니다. C로 구현돼 더 빠르고 버그가 없어요.

from itertools import permutations

list(permutations([1, 2, 3]))       # 전체 순열: (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)
list(permutations([1, 2, 3], 2))    # 길이 2 순열(N과 M): (1,2) (1,3) (2,1) (2,3) (3,1) (3,2)

직접 구현은 리스트를, 내장은 튜플을 돌려주지만 값의 나열은 똑같습니다. 원리를 손으로 한 번 짜 봤기에, 내장이 "안 쓴 원소를 골라 자리를 채우고 있구나"를 알고 쓸 수 있어요. 이게 이 과목이 매번 직접 구현과 내장을 짝지어 보여 주는 이유입니다.

💡 한 줄 정리

순열은 순서를 따지는 나열(n!개)이다. 안 쓴 원소를 used로 체크하며 자리를 채우고, 돌아와 표시를 되돌린다(백트래킹). 실전에선 itertools.permutations를 쓴다.

Step 5: "순서가 없는 선택" (조합)

순열이 "순서를 따지는 나열"이었다면, 조합(combination)은 순서를 따지지 않는 선택입니다. [1, 2]와 [2, 1]을 같은 것으로 봐요. 세 사람 중 두 명을 뽑아 팀을 만드는데, 누구를 먼저 뽑았는지는 중요하지 않은 상황이죠. n개에서 r개를 고르는 조합의 수를 nCr이라고 씁니다.

순열과 조합의 코드는 비슷해 보이지만 결정적인 차이가 하나 있어요. start 인덱스입니다.

# algorithms/backtracking.py
def combinations(items, r):
    n = len(items)
    result = []
    current = []

    def backtrack(start):
        if len(current) == r:           # 종료 조건: r개를 다 골랐다
            result.append(current[:])
            return
        for i in range(start, n):       # start부터 — 뒤에서만 골라 순서 중복 제거
            current.append(items[i])
            backtrack(i + 1)
            current.pop()               # 되돌리기(백트래킹)

    backtrack(0)
    return result

순열엔 used 배열이 있었는데, 조합엔 없죠? 대신 backtrack(start)가 있습니다. 다음 원소를 고를 때 항상 "지금 고른 자리보다 뒤에서만"(i + 1부터) 고르게 강제해요. 이렇게 하면 [1, 2]는 나오지만 [2, 1]은 절대 안 나옵니다 — 2를 고른 뒤엔 그 뒤(3)만 볼 수 있으니 1로 되돌아가지 않거든요. 순서가 뒤집힌 중복을 이 한 줄로 원천 봉쇄하는 겁니다.

 조합 combinations([1, 2, 3, 4], 2) — start 뒤에서만 골라 순서 중복을 막는다

 1 ─┬ 2 → [1, 2]
    ├ 3 → [1, 3]
    └ 4 → [1, 4]
 2 ─┬ 3 → [2, 3]      (1로 되돌아가지 않는다 — 2 뒤만 본다)
    └ 4 → [2, 4]
 3 ─┴ 4 → [3, 4]
                       → 4C2 = 6개

itertools.combinations가 같은 일을 합니다. 실전에선 이걸 쓰세요.

from itertools import combinations

list(combinations([1, 2, 3, 4], 2))   # (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) — 6개

정리하면, 순열과 조합을 가르는 질문은 딱 하나예요. "순서를 따지나?" 따지면 순열(used로 안 쓴 것 고르기), 안 따지면 조합(start로 뒤에서만 고르기)입니다. 이 구분이 "N과 M" 계열 문제에서 순열형과 조합형을 알아보는 눈이 됩니다.

💡 한 줄 정리

조합은 순서를 무시하는 선택(nCr개)이다. start 인덱스로 "뒤에서만" 골라 순서가 뒤집힌 중복을 원천 봉쇄한다. 그래서 조합엔 used 배열이 필요 없다.

Step 6: "가망 없으면 되돌아간다" (백트래킹)

지금까지 완전탐색은 "모든 경우를 다 만들고 나서" 답을 골랐습니다. 부분집합 2ⁿ개, 순열 n!개를 전부 만든 뒤 확인했죠. 그런데 다 만들 필요가 없는 경우가 많아요. 만드는 도중에 "이 가지로는 절대 답이 안 나온다"는 게 보이면, 거기서 멈추고 되돌아가면 됩니다. 이게 백트래킹(backtracking)입니다. 가망 없는 가지를 미리 쳐 내는 걸 가지치기(pruning)라고 불러요.

부분집합의 합으로 봅시다. "음이 아닌 정수 목록에서, 합이 정확히 target인 부분집합이 있나?" 완전탐색이라면 부분집합을 2ⁿ개 다 만들어 합을 확인할 거예요. 백트래킹은 다릅니다. 원소를 하나씩 더해 가다가, 남은 목표가 음수로 떨어지면 그 아래로는 절대 target을 못 맞추니 즉시 되돌아갑니다.

# algorithms/backtracking.py
def subset_sum(nums, target):
    n = len(nums)

    def backtrack(i, remaining):
        if remaining == 0:              # 종료 조건: 목표를 정확히 맞췄다
            return True
        if i == n or remaining < 0:     # 다 봤거나, 넘어섰으면(가지치기) 실패
            return False
        # 가지 1: nums[i]를 쓴다 / 가지 2: 안 쓴다 — 하나라도 True면 True
        return backtrack(i + 1, remaining - nums[i]) or backtrack(i + 1, remaining)

    return backtrack(0, target)

remaining은 "앞으로 더 채워야 할 남은 목표"예요. 0이 되면 정확히 맞춘 거라 True(종료 조건). 그런데 remaining < 0이 핵심입니다. nums가 음이 아닌 정수라, 남은 목표가 음수로 떨어졌다는 건 이미 target을 넘어섰다는 뜻이에요. 그 아래로 아무리 더해 봐야 0으로 돌아올 수 없으니, 그 가지를 통째로 접습니다. 이 한 줄이 탐색 나무의 큰 가지를 뭉텅 쳐 내요.

 subset_sum([2, 4, 6], target=5) — 남은 목표가 음수면 그 가지를 통째로 접는다

 remaining = 5
 ├─ 2 쓰기 → 3
 │   ├─ 4 쓰기 → -1      ← 음수! 가지치기 (아래로 안 내려간다)
 │   └─ 4 빼기 → 3
 │       ├─ 6 쓰기 → -3  ← 음수! 가지치기
 │       └─ 6 빼기 → 3   ← 0이 아니다, 실패
 └─ 2 빼기 → 5
     └─ (4, 6으로도 5를 못 맞춘다) → 최종 False

4 쓰기 → -1에서 가지를 접은 덕분에, 그 아래로 6을 넣느냐 마느냐 두 경우를 아예 안 봤어요. 완전탐색이라면 봤을 가지입니다. 이렇게 백트래킹은 헛일을 줄여요.

완전탐색 vs 백트래킹 — 빅오는 같은데 왜 쓰나

여기서 정직하게 짚을 게 있습니다. 백트래킹의 최악 시간 복잡도는 여전히 O(2ⁿ)예요. 가지치기가 하나도 안 먹히는 최악의 입력이 있을 수 있으니까요. 그럼 왜 쓰냐? 실제 입력에서는 가지치기가 큰 가지를 쳐 내 평균적으로 훨씬 빠르기 때문입니다. 최악은 같아도 보통은 완전탐색보다 월등히 적게 뒤져요.

   완전탐색       모든 경우를 끝까지 다 만든다      2ⁿ개 전부
   백트래킹       가망 없으면 도중에 되돌아간다     최악 2ⁿ, 실제론 훨씬 적게

   핵심: 백트래킹 = 완전탐색 + 가지치기. 빅오의 상한은 같아도,
        '유망하지 않으면 안 내려간다'가 실전의 속도를 가른다.

그래서 가지치기를 잘 설계하는 게 백트래킹의 실력입니다. "이 가지는 더 볼 필요가 없다"는 조건(유망성 판단)을 얼마나 날카롭게 잡느냐가 관건이에요. 다음 Step의 N-Queen이 이 가지치기의 힘을 제대로 보여 줍니다.

💡 한 줄 정리

백트래킹은 완전탐색에 가지치기를 더한다. 만드는 도중 가망 없는 가지(subset_sum의 remaining < 0)를 접어 헛일을 줄인다. 최악 복잡도는 O(2ⁿ)로 같아도 실전 속도가 갈린다.

Step 7: "체스판 위의 백트래킹" (N-Queen)

백트래킹의 결정판, N-Queen 문제입니다. n×n 체스판에 퀸 n개를, 서로 공격하지 못하게 놓는 모든 방법을 찾는 문제예요. 체스에서 퀸은 같은 행·같은 열·같은 대각선을 전부 공격합니다. 그러니 어떤 두 퀸도 같은 행·열·대각선에 있으면 안 돼요.

접근은 이렇습니다. 한 행에 퀸을 하나씩, 위에서 아래로 순서대로 놓습니다. 한 행엔 하나만 놓으니 같은 행 충돌은 자동으로 없어져요. 남은 건 열과 대각선입니다. 새 퀸을 놓기 전에, 이미 놓은 윗행 퀸들과 같은 열이거나 같은 대각선이면 그 자리는 건너뜁니다(가지치기). 안전한 칸에만 놓고 다음 행으로 내려가요.

# algorithms/backtracking.py
def solve_n_queens(n):
    result = []
    cols = []                       # cols[r] = r행에 놓은 퀸의 열

    def is_safe(row, col):
        for r in range(row):        # 이미 놓은 윗행들과만 비교하면 된다
            c = cols[r]
            if c == col or abs(row - r) == abs(col - c):
                return False        # 같은 열 또는 같은 대각선 → 놓을 수 없다
        return True

    def backtrack(row):
        if row == n:                # 종료 조건: n개를 모두 놓았다
            result.append(cols[:])
            return
        for col in range(n):
            if is_safe(row, col):   # 안전한 칸만 가지로 뻗는다(가지치기)
                cols.append(col)
                backtrack(row + 1)
                cols.pop()          # 되돌리기(백트래킹)

    backtrack(0)
    return result

cols가 답을 담는 방식이 산뜻합니다. 인덱스가 행, 값이 열이에요. cols = [1, 3, 0, 2]는 "0행 1열, 1행 3열, 2행 0열, 3행 2열에 퀸"이라는 뜻입니다. 한 행에 하나씩 놓으니 이 한 줄로 배치가 완전히 표현돼요.

가지치기의 심장은 is_safe입니다. 특히 대각선 판정이 예뻐요. 두 퀸이 같은 대각선에 있다는 건 행의 차이와 열의 차이가 같다는 뜻입니다(abs(row - r) == abs(col - c)). 대각선은 45도로 뻗으니 행이 1 내려갈 때 열도 1 움직이거든요. 이 조건에 걸리면 그 칸은 포기하고 다음 열로 넘어갑니다.

 4-Queen 한 해 — cols = [1, 3, 0, 2] (행마다 퀸의 열)

     0   1   2   3      (열 인덱스)
   +---+---+---+---+
 0 | . | Q | . | . |    0행 → 1열
   +---+---+---+---+
 1 | . | . | . | Q |    1행 → 3열
   +---+---+---+---+
 2 | Q | . | . | . |    2행 → 0열
   +---+---+---+---+
 3 | . | . | Q | . |    3행 → 2열
   +---+---+---+---+

 어떤 두 Q도 같은 열·같은 대각선에 없다. 이게 안전한 배치.

이 코드가 실제로 잘 도는지 코드베이스에서 확인해 보면, 4-Queen은 해가 2개, 8-Queen은 그 유명한 92개가 나옵니다. 2×2와 3×3은 아무리 놓아도 조건을 못 맞춰 해가 0개예요. 최악 시간은 O(n!)이지만, is_safe 가지치기가 안 되는 배치를 미리 쳐 내 실제 탐색은 그보다 훨씬 적습니다. 만약 가지치기 없이 n개 퀸을 n²칸에 완전탐색으로 다 놓아 봤다면 훨씬 오래 걸렸을 거예요. N-Queen은 "가지치기가 실전 속도를 어떻게 바꾸는지"를 눈으로 보여 주는 대표 문제입니다.

💡 한 줄 정리

N-Queen은 한 행에 퀸을 하나씩 놓으며, 같은 열이나 같은 대각선이면 즉시 되돌아간다(가지치기). 대각선 충돌은 두 퀸의 행 차이와 열 차이가 같은지로 판정한다. n=8이 92해다.

Step 8: 정리 — 재귀·완전탐색·백트래킹, 언제 무엇을

오늘 하루를 한 장으로 정리해 봅시다. 세 개념이 층층이 쌓였어요.

 재귀        함수가 자기를 부른다 — 종료 조건 + 자기 호출. 호출 스택 위에서 돈다.
   │
   ├ 완전탐색   재귀로 모든 경우를 다 만든다 — 부분집합 2ⁿ, 순열 n!, 조합 nCr.
   │            n이 작을 때(≤ 20쯤)의 정직하고 안전한 답.
   │
   └ 백트래킹   완전탐색 + 가지치기 — 가망 없는 가지를 도중에 접는다.
                최악은 같아도 실전에선 훨씬 빠르다.

문제를 만났을 때 무엇을 꺼낼지, 신호로 정리하면 이렇습니다.

그리고 마지막으로, 오늘 배운 재귀 호출 스택이 곧장 다음 시간으로 이어집니다. 완전탐색을 "그래프 위에서" 하면 그게 바로 DFS(깊이 우선 탐색)예요. 다음 시간(E-2)엔 C-3에서 배운 그래프 표현 위에, 오늘의 재귀를 얹어 DFS와 BFS로 미로를 뒤지고 최단 경로를 찾습니다. 오늘의 "쌓였다 되돌아가는" 그 호출 스택 그림이 그대로 DFS의 심장이 됩니다.

💡 한 줄 정리

재귀로 모든 경우를 펼치고(완전탐색), 그 펼침에서 가망 없는 가지를 접는다(백트래킹). 문제를 만나면 n의 크기를 보고 완전탐색이 되는지부터 판단한다.

마무리

오늘은 카테고리 E(알고리즘 패러다임)의 문을 열며, "영리한 지름길이 없으면 다 뒤진다"는 완전탐색과 그 뼈대인 재귀, 그리고 헛일을 줄이는 백트래킹을 손에 익혔습니다. 지난 시간까지 O(n)의 우아함을 봤다면, 오늘은 O(2ⁿ)·O(n!)의 폭발과 그걸 다루는 법을 만났어요.

오늘 배운 핵심 세 가지

• 💡 하나 — 재귀는 두 기둥으로 선다. 종료 조건(base case)에서 멈추고, 자기 호출로 큰 문제를 작은 문제로 미룬다. 호출이 스택에 쌓였다 종료 조건에서 거꾸로 풀리며(unwind) 답이 위로 전달된다. 이 그림이 완전탐색·백트래킹·다음 시간 DFS의 공통 바탕이다.
• 💡 둘 — 완전탐색은 모든 경우를 다 만든다. 부분집합은 각 원소를 넣거나 빼서 2ⁿ개, 순열은 순서를 따져 n!개, 조합은 순서를 무시해 nCr개. 경우의 수가 폭발하니 "n이 작다"가 전제고, 그 판단은 "1초 1억" 잣대로 한다.
• 💡 셋 — 백트래킹은 완전탐색에 가지치기를 더한다. 만드는 도중 가망 없는 가지를 접어(subset_sum의 음수, N-Queen의 열·대각선) 헛일을 줄인다. 최악 복잡도는 같아도 실전 속도가 갈린다.

돌아보면 오늘의 한 줄기는 "재귀 → 완전탐색 → 백트래킹"이었어요. 자기를 부르는 재귀로 모든 경우를 펼치고(완전탐색), 그 펼침에서 가망 없는 가지를 접는(백트래킹) 흐름입니다. 이 세 층이 앞으로 배울 DFS/BFS(E-2)·분할정복(E-3)·동적 계획법(E-4)의 바닥에 전부 깔려 있습니다.

다음 시간 예고

오늘 완전탐색을 "부분집합·순열" 같은 추상적인 나열에서 해 봤다면, 다음 시간(E-2)엔 그 완전탐색을 그래프 위에서 합니다. C-3에서 배운 그래프(정점과 간선) 위를, 오늘의 재귀를 얹어 깊이 우선으로 파고드는 DFS와, 큐로 넓게 퍼지는 BFS로 뒤져요. 미로에서 출구를 찾고, 섬의 개수를 세고, 가중치 없는 그래프에서 최단 경로를 구합니다. 오늘의 재귀 호출 스택이 DFS로, B-1의 큐가 BFS로 곧장 이어지니, 오늘 그림을 잘 챙겨 두세요.

과제

오늘 배운 재귀·완전탐색·백트래킹을 손에 붙이는 문제들입니다. 코드베이스 algorithms/backtracking.py의 함수를 가져다 쓰거나 직접 짜서 풀어 보세요. 각 문제의 시간·공간 복잡도를 빅오로 함께 적는 걸 잊지 마세요.

[기초] 재귀로 거듭제곱 구하기

밑 base와 지수 exp(0 이상 정수)가 주어질 때 base의 exp제곱을 재귀로 구하는 power(base, exp)를 작성하세요. 예를 들어 power(2, 10)은 1024, power(3, 0)은 1, power(5, 1)은 5입니다. 반복문이나 ** 연산자 없이, 재귀만으로 푸세요.

• 종료 조건부터 정하세요. "지수가 0이면 무엇을 돌려줘야 하는가?" 이게 재귀의 바닥입니다.
• 점화식은 "base^exp = base × base^(exp-1)"입니다. Step 1의 factorial과 완전히 같은 골격이에요.
• 이 재귀의 시간·공간 복잡도를 빅오로 적고, 왜 공간이 O(exp)인지(호출 스택) 한 줄로 설명하세요.

[응용] 합이 target인 부분 수열의 개수

정수 목록 nums와 값 target이 주어질 때, 원소를 골라 만든 부분집합 중 합이 정확히 target인 것의 개수를 세는 count_subset_sum(nums, target)을 백트래킹으로 작성하세요. 예를 들어 count_subset_sum([1, 2, 3], 3)은 2([3]과 [1, 2]), count_subset_sum([3, 34, 4, 12, 5, 2], 9)는 2([4, 5]와 [3, 4, 2])입니다.

• Step 6의 subset_sum은 존재하면 True를 돌려줬죠. 이번엔 True/False가 아니라 "몇 가지인가"를 셉니다. "쓴다/안 쓴다" 두 가지의 결과를 더해 올리세요.
• 코딩테스트의 "부분 수열의 합" 유형이 이 골격입니다(프로그래머스·백준에 자주 나와요).
• 시간 복잡도를 빅오로 적고, nums의 크기 n이 어디까지면 이 완전탐색이 "1초 1억" 안에 드는지 함께 적으세요.

[심화] 올바른 괄호 만들기

여는 괄호와 닫는 괄호가 각각 n개씩일 때, 짝이 맞는 올바른 괄호 문자열을 모두 만들어 반환하는 generate_parentheses(n)을 백트래킹으로 작성하세요. 예를 들어 generate_parentheses(2)는 ["(())", "()()"](순서는 무관), generate_parentheses(1)은 ["()"], generate_parentheses(3)은 5가지입니다.

• 완전탐색이라면 여는/닫는 괄호를 아무렇게나 2n개 늘어놓고(2^(2n)가지) 올바른지 검사할 거예요. 하지만 대부분이 잘못된 괄호라 헛일입니다. 여기에 가지치기를 넣으세요.
• 가지치기 두 조건을 생각해 보세요. ① 여는 괄호는 아직 n개 미만일 때만 더 넣을 수 있다. ② 닫는 괄호는 지금까지 넣은 여는 괄호 수보다 적을 때만 넣을 수 있다(안 그러면 짝이 안 맞아요). 이 두 조건이 잘못된 가지를 미리 쳐 냅니다.
• 이렇게 가지치기한 백트래킹이, 아무렇게나 만들어 검사하는 완전탐색보다 왜 훨씬 빠른지 Step 6의 논리로 설명하세요.

생각해볼 주제

1. 모든 재귀는 반복으로 바꿀 수 있다는데, 그럼 재귀는 왜 쓰나

이론적으로 어떤 재귀든 직접 스택을 들고 다니면 반복으로 바꿀 수 있습니다. 반복은 호출 스택을 안 써서 깊이 한계(약 1000)에 안 걸리고 공간도 O(1)이죠. 그런데도 우리는 트리 순회나 백트래킹을 재귀로 짭니다. 무엇이 재귀를 선택하게 만들까요? "점화식이 코드에 그대로 드러난다"는 가독성의 이득과, "깊이가 깊으면 터진다"는 위험 사이에서, 언제 재귀를 고르고 언제 반복으로 바꿀지 그 판단 기준을 정리해 보세요. Step 2의 트레이드오프 표가 출발점입니다.

2. 가지치기는 최악 복잡도 O(2ⁿ)를 못 줄이는데, 왜 의미가 있을까

백트래킹의 가지치기는 최악의 경우 시간 복잡도를 바꾸지 못합니다. 가지치기가 하나도 안 먹히는 입력이 존재할 수 있으니, 상한은 여전히 완전탐색과 같은 O(2ⁿ)·O(n!)이에요. 그런데도 N-Queen이나 부분집합 합에서 가지치기는 실전 속도를 극적으로 바꿉니다. "최악 복잡도는 같은데 실제로는 훨씬 빠르다"는 이 간극을 어떻게 이해해야 할까요? 최악(worst case)과 평균(average case)의 차이, 그리고 코딩테스트의 시간 제한이 최악이 아니라 "주어진 입력"에 대한 것이라는 점을 엮어 생각해 보세요.

3. n이 작으면 완전탐색이 오히려 정답이다 — 섣부른 최적화의 경계

경험이 쌓이면 "완전탐색은 느리다"는 인상 때문에 처음부터 영리한 방법을 찾으려는 유혹이 생깁니다. 그런데 n이 15라면? 2¹⁵는 약 3만이라 완전탐색이 순식간이고, 코드가 짧고 틀릴 여지도 적어요. 이럴 때 굳이 복잡한 최적화를 얹는 건 시간 낭비이자 버그의 씨앗일 수 있습니다. 입력 크기 n을 보고 "완전탐색으로 충분한지, 아니면 정말 더 영리한 방법이 필요한지"를 가르는 경계는 어디일까요? "1초 1억" 잣대와 "코드의 단순함이 주는 안전"을 함께 저울에 올려 생각해 보세요.