되추적 알고리즘의 기본 원리는 미로의 갈림길에서 경로를 표시하면 시간을 절약할 수 있는 이러한 표시를 이용함

0-1 배낭 채우기 문제를 다루는 한 가지 방법은 실제 해답후보의 부분집합들을 모두 생성하면 되지만, 이는 마치 미로에서 모든 경로를 막힌 곳이 나올 때까지 무작정 따라가 보는 것과 마찬가지임

→ 이 부분집합의 개수는 $2^n$이 되므로 n이 작은 경우에만 통함

→ 그러나 부분집합을 생성하면서 생성할 필요가 없는 것들을 알 수 있다면 불필요한 노력을 절감할 수 있을 것

→ 이게 되추적 알고리즘임.

따라서 0-1 배낭 채우기 문제와 같은 부류의 문제를 푸는 되추적 알고리즘은 그래도 최악의 경우 지수시간임

→ 하지만 모든 경우 효율적이지는 않지만 많은 경우 효율적일 수 있기 때문에 유용하게 쓰임.

5.1 되추적 기술

되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용함

되추적의 전형적인 사례는 서양장기의 n-여왕말 문제임

• 목표: n x n 크기의 서양 장기판에 서로 잡아먹히지 않도록 n개의 여왕말을 위치시키는 것
• 즉, 어떤 여왕말끼리도 같은 행이나 열이나, 대각선상에 위치할 수 없음

→ 여기서 순서 = 여왕 말을 둘 n개의 각각 다른 위치

→ 집합 = 서양 장기판에서 말을 둘 수 있는 $n^2$개의 위치들

→ 기준 = 어떤 여왕말도 서로 잡아먹히지 말아야 한다는 것