백트래킹

[heerucan]

Backtracking

DFS와 차이점은 (불필요한 탐색을 하지 않음)

132 / 123/ 234에서 123을 찾는다고 하면

• DFS의 경우, 132에 접근 시에도 십의 자리 수가 달라도 일의 자리까지 즉, 트리의 바닥에 도달할 때까지 탐색을 계속한다.
• 백트래킹은 132에 접근 시 123과 다르면 바로 탐색을 종료하고, 다음 수로 넘어간다.

• 재귀로 생각하는 것이 자연스럽다.
• DP의 경우 문제가 작은 문제고 쪼개지고, 문제에 대한 답을 메모했다면,
• 백트래킹은 모든 경우의 수를 하나씩 살펴봄, 그리고 그 가능성을 체크하면서 더이상 계산할 필요가 없다고 판단하면 다시 Decision Space를 만들고, 다시 반복

시간복잡도는?