[알고리즘 이론] 백트래킹(Backtracking)

이론

 이번에 볼 알고리즘은 백트래킹이다. 백트래킹을 알아두면 대부분 해를 찾는데 도움이 될것이다. 백트레킹은 탐색하는 도중 중복되거나 해를 찾는 방향이 맞지 안 맞으면 그 부분을 탐색하지않는다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 이러면 불필요한 탐색을 할 필요가 없어서 기존 완전 탐색보다  시간적이나 메모리가 단축할수 있다. 자세한것은 아래 사이트에서 확인해보면된다.

https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89

퇴각검색 - 위키백과, 우리 모두의 백과사전