백트래킹1 백트래킹(BackTracking)의 개념과 DFS와의 차이 백트래킹(BackTracking)의 정의 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색한다. 해가 아니거나 다시 돌아가서(=back) 최적의 해를 찾는다. 백트래킹의 구현 보통 백트래킹의 구현은 BFS와 DFS와 함께 구현한다. 재귀로 보통 구현되고, 재귀 함수가 호출되고 조건에 맞지 않으면 종료되고 그전에 호출된 재귀로 돌아오므로, 백트래킹에서 말하는 ‘가능성이 없으면 후보를 포기해 정답을 찾아가는’ 방식이다. 안되는 조건은 없애면서 탐색하기 때문에 시간복잡도가 선형적으로 증가할 법한 문제에서 백트래킹을 적용하면 시간복잡도를 줄일 수 있다. 모든 경우의 수에서 한정 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전 탐색 기법인 BFS와 DFS가 모두 구현이 가능하다. 하지만 한정 조건에 부합.. 2023. 4. 11. 이전 1 다음
