반응형 백트래킹1 백트래킹 저번 시간에 DFS, BFS 에서 다뤘는데 이들은 모든 노드를 참조한다는 그런 탐색 방법이다. 하지만 이미 조건에서 벗어난 경우에도 나머지 노드들을 탐색을 계속해서 진행해야할까? 그럴경우엔 괜히 자원 낭비가 될수가 있다. 이럴때 사용하는것이 백트래킹 기술이다. 백트래킹(Backtracking)즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됨 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 해를 .. 2022. 8. 5. 이전 1 다음 반응형