백트래킹이란? (Backtracking)

<aside> 💡 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제에 특히 유용하다.

</aside>

• DFS보다 좀더 넓은 의미를 가지며 DFS는 백트래킹의 골격을 이루고 있는 알고리즘이다.
• 브루트포스 방식과는 다르게 가능성이 없는 경우에는 후보를 포기한다는 점에서 더 나은 방식이라고 할 수 있다.
• 간단히 말해 필요 없는 후보를 가지치기를 함으로써 시간복잡도를 줄이는 방법을 말한다.