프로그래밍을 하다 보면 "모든 경우의 수를 탐색해야 하는 문제"를 자주 만나게 됩니다. 이럴 때 유용하게 쓰이는 기법 중 하나가 바로 백트래킹(Backtracking)입니다.백트래킹은 말 그대로 "되돌아가기"입니다. 어떤 문제를 풀기 위해 가능한 선택지를 따라가다가, 그 선택이 정답으로 이어지지 않으면 다시 돌아가 다른 선택지를 탐색하는 방식입니다.즉, 가능한 모든 경우를 탐색하지만, 유망하지 않은 경로는 조기에 포기(가지치기)하면서 효율적으로 답을 찾아나갑니다.완전탐색의 일종이지만, 불필요한 경우를 줄이는 전략을 포함하고 있는 것이 차별점입니다. Q. 언제 백트래킹을 사용하지? 가능한 모든 조합, 순열, 부분집합 등을 구해야 할 때퍼즐, 미로 찾기, N-Queen, 스도쿠 등에서탐색 과정에서 제약 조건..