백트래킹(Backtracking) 이란 백트래킹 이란 모든 경우의 수를 전부 고려하는 알고리즘 이다. 조금 더 자세하게 말하자면 현재 상태에서 가능한 모든 후보군을 따라가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적 알고리즘이라고 한다. 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 백트래킹을 사용해 해결할 수 있는 문제는 주로 검색, 의사 결정, 최적화, 열거하기 등의 문제가 있다. 사실 백트래킹은 사용 가능한 경우가 많지만 시간복잡도가 보통 $2^n$ 이기 때문에 대부분의 문제는 동적 프로그래밍 또는 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다. 그렇다고해서 백트래킹을 사용하..