백트래킹

🤷‍♂️ 백트래킹(Backtracking) 알고리즘모든 경우의 수를 전부 고려하는 알고리즘으로 트리형 자료구조에 적합하며 계속해서 답이 될 수 있는 후보 노드들을 만들어내고, 해당 후보로는 적절한 답을 얻을 수 없는 후보를 철회("Backtracks")하면서 문제를 해결하는 알고리즘이다. 가장 유명한 예제로는 서로를 공격할 수 없는 8개의 퀸의 위치 배열을 찾는 N-queens 문제가 있다. N-queens 문제를 백트래킹 알고리즘으로 접근하면, 첫 행부터 아래로 내려가면서, 이미 존재하는 퀸에 가로 세로 대각선에 존재하는 후보는 철회하는 방식으로 풀 수 있다. 백트래킹 알고리즘은 '부분적 후보 해결책'의 개념을 확인하는 문제와 그것이 유효한 해결책으로 완성될 수 있는 지의 여부를 상대적으로 빠르게 시험..