목록backtracking (1)

처음부터 차근차근

[알고리즘] Backtracking, N-Queen 문제

Backtracking이란?? 해(답)을 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가서 다시 해를 찾아가는 기법을 의미한다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 주로 DFS 등 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤, 그 이전으로 돌아가서 다시 다른 경우를 탐색하게 구현할 수 있다. 백트래킹 기법의 유망성 판단 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking..
CS/알고리즘 2023. 11. 16. 15:11
이전 Prev 1 Next 다음