목록백트래킹 (1)

유블로그

[알고리즘] 백트래킹(Backtracking)

- 백트래킹 여러 가지 선택지들이 존재하는 상황에서 한 가지 선택 선택하면 새로운 선택지들 집합이 생성됨 선택들을 반복하며 최종 상태에 도달 - 백트래킹과 완전탐색(DFS)의 차이 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다.(가지치기) 완전 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단한다. N! 가지의 경우의 수 같이 완전 탐색 하기 힘들 때 좋다. 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 최악의 경우에는 지수함수 시간을 요하므로 처리 불가능할 수 있다.
알고리즘 2020. 8. 27. 14:09
이전 Prev 1 Next 다음