백트래킹(Backtracking)
백트래킹 알고리즘은 모든 경우의 수를 탐색하되, 불가능한 경우의 수는 가지치기하여 효율적으로 문제를 해결하는 알고리즘입니다. 모든 경우의 수를 탐색하기 때문에 브루트 포스 알고리즘과 유사하지만, 불가능한 경우의 수를 가지치기하여 시간 복잡도를 줄일 수 있습니다. 그래서 ‘가지치기 알고리즘’ 이라고도 한다.
백트래킹 구현방식
- 가능한 경우의 수를 생성합니다.
- 생성된 경우의 수를 검사합니다.
- 검사한 경우의 수가 문제의 조건을 만족하면 정답으로 출력합니다.
- 검사한 경우의 수가 문제의 조건을 만족하지 않으면 가지 치기 합니다.
