Backtracking
설명
백트래킹은 모든 조합을 시도해서 문제의 해를 찾는 알고리즘이다. 이 알고리즘이 장점이 될 수 있는 이유는 백트래킹 구현 방법들이 많은 부분 조합들을 배제하기 때문이다. 즉, 이 말이 무엇이냐! 간단한 이진트리를 생각해보면, dfs방식으로 해를 찾는데, 노드를 하나하나 확인할 때마다 가능한 노드만 방문한다는 것이다. 즉, 모든 노드를 확인하는 것 같겠지만 특정 조건에 만족하는 노드만 방문하는 것이다. 따라서 풀이 시간이 단축 될 수 있다!
구현
백트래킹은 보통 재귀 함수로 구현이 된다. 문제마다 다르겠지만, 하나 이상의 변수로 현재의 상태를 보관하거나 과거의 상태를 불러 올 수 있는 작업이 요하는 경우가 많다.
백트래킹 관련된 예시문제들은 15649, 15650, 15651, 15652, nqueen, 스도쿠 문제들을 참고하면 된다.