백트래킹 설명

1. 백트래킹이란

완전탐색과 유사하지만 조건과 달성 가능성을 고려해 케이스를 줄이는 경우를 의미한다. 하지만 결국 시간 복잡도 자체를 줄이지는 못하므로 차수가 아닌 계수를 줄여 소요 시간을 줄여야 하기 때문에 재귀나 반복문을 문제에서 원하는대로 적절하게 작성하는 능력이 핵심이다. 완전 탐색이 단순한 반복문이라면 백트래킹은 별찍기로 비유할 수 있을 것 같다. 백트래킹 = 완전탐색 응용

2. 문제 풀이

1. N-Queen 가장 대표적인 문제로 백트래킹과 완전탐색의 차이가 어떤 것인지 알 수 있다.
2. 스도쿠 실생활에서 가장 쓸모(?)가 많다. 중학교 때 이거 폰에 넣어가서 수학 시간 스도쿠 퀴즈 날먹
3. N과 M 시리즈 탐색의 순서를 강제하거나 제약 조건을 거는 연습 문제 시리즈
   • N과 M 1
   • N과 M 2
   • N과 M 3
   • N과 M 4
4. 연산자 끼워넣기 위의 문제들을 모두 풀었다면 쉽게 풀 수 있다.
5. 스타트와 링크 응용