백트래킹
2020. 3. 27.
@ 백트래킹(Backtracking) 백트래킹 (Backtracking) 해를 찾는 도중(완전탐색 중, 모든 경우를 따져보고 있는데...) 그 길이 막히면(더 고려해 볼 필요가 없을 때) 가던 길 경로를 포기하고 되돌아와 다른 길로부터 가며 ... 해를 찾는 기법 최적화(optimization) ,결정(decision) 문제 해결 (서로 상호 연결된 같은 문제...) 최적화(optimization) 문제 : 조건에 만족하는 (최단으로 가는 경로) 답을 찾으세요. 결정(decision) 문제 : 문제의 조건에 만족하는 해의 존재 있냐 없냐 (예스 올 노) 예제 문제 ) 미로찾기, n-Queen , 부분집합, 순열 관련 문제, 4컬러링 백트래킹 구현 방법 ) DFS, BFS 를 하는데 가지치기를 할 뿐.....