Backtracking1 백트래킹 근래에 꾸준한 공부 습관을 다시금 들이고자 틈틈이 알고리즘 문제를 풀고 있다. 그러던 와중, '백트래킹'에 대해 조금 공부하게 되어 개념과 푼 문제를 간단하게 정리해보려 한다. 백트래킹(Backtracking) 현재 상황에서 탐색 가능한 모든 경로를 다 탐색하다, 조건에 맞지 않는 경로를 탐색하게 될 경우 다시 뒤로 돌아가서 다른 경로를 탐색하는 알고리즘. 이 때 해결하려는 문제는 트리 구조로 표현되며, 이를 탐색하는 데에는 깊이 우선 탐색을 사용한다. DFS와는 달리 조건(한정 조건이라고 하는 듯)에 맞지 않는 해가 나오면 이전으로 돌아가기 때문에 최종적으로 탐색 시간이 줄어든다는 특징이 있음. 백트래킹을 접하며 참고했던 어느 블로그에서 DFS와 백트래킹을 유사점(교차점)이 있는 교집합 관계같다 표현한.. 2023. 10. 15. 이전 1 다음
