backtracking이란 무엇인가요?

Question

Accepted Answer

**Backtracking(백트래킹)**은 후보 해를 점진적으로 구성하고, 부분 후보가 유효한 해로 이어질 수 없다고 판단되는 즉시 그것을 **버립니다(되돌아갑니다)**. DFS를 통해 해 공간을 체계적으로 탐색하며 막다른 길을 가지치기합니다.

## 개념

선택 -> 탐색 -> 선택 취소. 한 선택지를 시도하고 재귀합니다. 실패하면 되돌리고 다음을 시도합니다.

## 예시: 모든 순열

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # 완성된 해
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # 선택
            backtrack(path, remaining[:i] + remaining[i+1:])  # 탐색
            path.pop()                             # 선택 취소 (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6개의 순열
```

## 전형적인 문제

- **N-queens**, 스도쿠, 기사의 여행.
- **부분집합 / 조합 / 순열.**
- **단어 검색**, 미로 풀기.

## 복잡도

흔히 지수적입니다(예: 순열의 경우 O(n!)), 하지만 **가지치기**가 실질적인 탐색을 극적으로 줄입니다.

## 언제 사용하나 / 함정

제약 충족 문제와 "모든 유효한 구성 찾기" 문제에 사용하세요. 핵심 이점은 **조기 가지치기**입니다 — 제약을 위반하는 분기를 건너뜁니다. 상태를 되돌리는 것("선택 취소")을 잊는 것이 전형적인 버그입니다.

## 왜 중요한가

Backtracking은 후보를 누락하거나 반복하지 않고 조합적 공간을 탐색하는 체계적인 방법입니다.

좋은 가지치기는 다루기 힘든 brute force를 제 시간에 끝나는 것으로 바꿉니다.

업계 전반에서 퍼즐, 스케줄링, 제약 문제의 해결기를 뒷받침합니다.