🚦 이번 포스팅에서는 〰️ ▶️ 백트래킹(Backtracking)이란? ▶️ 백트래킹(Backtracking)문제 풀어보면서 익히기 📌 백트래킹(Backtracking)이란? : 해를 찾는 도중 해가 아니라서 막힌다면, 되돌아가서 다시 해를 찾는 기법. 최적화 문제와 결정 문제를 푸는 방법이 된다. --> 반복문의 횟수까지 줄일 수 있음 일명 가지치기(pruning)로, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 그러나, 문제가 N!의 경우의 수를 가질때 최악의 경우로 O(지수함수) 필요할 수 있다. 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 답이 될만한지 판단하고, 그렇지 않으면 가지치지한다. 주로, DFS 등 모든 경우의 수를 탐색하는 과정에서 조건문 등을 ..
