[C/Python] 백트래킹

1. 백트래킹이란?

모든 가능한 경우의 수를 탐색하되, **"유망하지 않은 경로"**를 미리 차단(Pruning, 가지치기)하여 효율적으로 해를 찾는 알고리즘입니다. 주로 **재귀(Recursion)**를 통해 구현하며, '가다가 막히면 되돌아온다'는 것이 핵심입니다.

---

2. 핵심 문제로 본 백트래킹의 진화

우리가 함께 푼 5가지 대표 문제를 통해 백트래킹의 발전 단계를 정리했습니다.

문제 유형	핵심 개념	주요 테크닉
N과 M 시리즈	순열과 조합	visited 배열, start 인자 사용
N-Queen	2차원 공간 제약	대각선 인덱스 공식 (r+c, r-c+n)
스도쿠	3중 제약 조건	상태 체크 배열 (행, 열, 3x3 박스)
연산자 끼워넣기	자원(개수) 관리	연산자 잔여 개수 기반 분기, 음수 나눗셈 처리
스타트와 링크	팀 나누기(조합)	대칭성 제거 (0번 항목 고정), 시너지 합산

---

3. 백트래킹의 3대 필수 요소 (Code Template)

모든 백트래킹 코드는 아래와 같은 공통 구조를 가집니다.

Python

 

def backtracking(depth):
    # 1. 기저 조건 (종료 조건)
    if depth == 목표치:
        결과 처리 및 출력
        return

    # 2. 하위 선택지 탐색
    for i in range(전체_범위):
        if 유망한가(i): # 가지치기 (Pruning)
            # 3. 상태 변화 (전진)
            visited[i] = True
            기록.append(i)

            backtracking(depth + 1) # 재귀 호출

            # 4. 상태 복구 (후퇴 - 가장 중요!)
            visited[i] = False
            기록.pop()

---

4. 성능 최적화의 비결 (Python vs C)

우리가 실습하며 배운 언어별 최적화 포인트입니다.

• Python (공간을 써서 시간을 산다)
  • itertools.combinations 등을 활용한 표준 라이브러리 최적화.
  • sys.exit(0)를 활용한 조기 종료.
  • 매번 루프를 돌며 체크하지 않고 **체크용 배열(Set/List)**을 미리 만들어 O(1)로 유망성 검사.
• C언어 (메모리 직관과 포인터)
  • Call by Reference: 결과값(min, max)을 주소로 넘겨 모든 재귀가 공유하게 함.
  • 전역 변수 활용: 함수 호출 시 스택 메모리 사용량을 줄여 성능 극대화.
  • 나눗셈 특성: C의 / 연산자는 0을 향해 절삭하므로 별도의 처리가 필요 없음.

---

5. 학습하며 얻은 깨달음

1. 초기값 설정: 최댓값을 찾을 땐 가능한 가장 작은 값으로, 최솟값은 가장 큰 값으로 시작해야 경계선 오류가 없습니다.
2. 원상복구의 중요성: 재귀에서 돌아온 뒤 상태를 다시 0이나 False로 돌려놓지 않으면, 다른 우주(경로)가 오염됩니다.
3. 인덱스 맞추기: 배열 크기를 N+1이나 10으로 잡아 실제 숫자와 인덱스를 일치시키면 버그를 획기적으로 줄일 수 있습니다.